Танд $n$ ширхэг бүхэл тоо бүхий $a_{i}$ цуваа болон $m$ ширхэг асуултууд өгөгджээ.Асуулт бүр нь 2 бүхэл тоо $(l_{j}, r_{j})$-аар өгөгдөнө.

Функцийг гэж тодорхойлъё.Уг функц нь зөвхөн $u ≤ v$-уудын хувьд тодорхойлогдсон.

Асуулт бүрийн хувьд $l_{j} ≤ x, y ≤ r_{j},  a_{x} ≤ a_{y}$ байх бүх тоонуудын $f(a_{x}, a_{y})$ функцийн утгуудын хамгийн их утгыг олно уу.

Оролт

Эхний мөрөнд цувааны урт болон асуултын тоог илэрхийлэх 2 бүхэл тоо $n, m$ ($1 ≤ n ≤ 5*10^{4},  1 ≤ m ≤ 5*10^{3}$) өгөгдөнө.

2-дахь мөрөнд $a$ цувааны элементүүд болох $n$ ширхэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 10^{6}$) өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд $j$-дэх асуултын параметрүүд болох 2 бүхэл тоо $l_{j}, r_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n$) өгөгдөнө.

Гаралт

Асуулт бүрийн хувьд $l_{j} ≤ x, y ≤ r_{j},  a_{x} ≤ a_{y}$ байх бүх тоонуудын $f(a_{x}, a_{y})$ функцийн утгуудын хамгийн их утга болох $a_{j}$-ыг салангид мөрөнд хэвлэнэ.