You are given an array with n integers a i and m queries. Each query is described by two integers (l j , r j ). Let's define the function . The function is defined for only u ≤ v . For each query print the maximal value of the function f(a x , a y ) over all l j ≤ x, y ≤ r j , a x ≤ a y .
输入描述:
The first line contains two integers n, m (1 ≤ n ≤ 5·104, 1 ≤ m ≤ 5·103) — the size of the array and the number of the queries.The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.Each of the next m lines contains two integers lj, rj (1 ≤ lj ≤ rj ≤ n) – the parameters of the j-th query.
输出描述:
For each query print the value aj on a separate line — the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj, ax ≤ ay.
示例1
输入
6 3<br />1 2 3 4 5 6<br />1 6<br />2 5<br />3 4<br />1 1<br />1<br />1 1<br />6 20<br />10 21312 2314 214 1 322<br />1 1<br />1 2<br />1 3<br />1 4<br />1 5<br />1 6<br />2 2<br />2 3<br />2 4<br />2 5<br />2 6<br />3 4<br />3 5<br />3 6<br />4 4<br />4 5<br />4 6<br />5 5<br />5 6<br />6 6<br />
输出
7<br />7<br />7<br />1<br />10<br />21313<br />21313<br />21313<br />21313<br />21313<br />21312<br />21313<br />21313<br />21313<br />21313<br />2314<br />2315<br />2315<br />214<br />215<br />323<br />1<br />323<br />322<br />
加载中...