오름차순

문제

길이 $MM$인 양의 정수열 $X_1,\dots ,X_{M}X\_1,\; \backslash dots\; ,\; X\_M$이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자. 수열 $X_1,\dots ,X_{M}X\_1,\; \backslash dots\; ,\; X\_M$이 오름차순이라는 것은, 각 $ii$ (1 ≤ i ≤ M - 1)에 대해 X_i ≤ X_{i+1}이라는 것이다.

수열 $XX$를 오름차순으로 만들기 위해, 수열 $XX$에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

• 어떤 $ii$ (1 ≤ i ≤ M)에 대해 $X_{i}X\_i$에 $22$를 곱한다.

연산을 최소 횟수로 적용해서 $XX$를 오름차순으로 만들 때, 이 최소 횟수를 $f(X)f(X)$라고 하자.

길이 $NN$의 양의 정수열 $A_1,\dots ,A_{N}A\_1,\; \backslash dots\; ,\; A\_N$과 쿼리 $QQ$개가 주어진다. 각 쿼리에는 1 ≤ l ≤ r ≤ N을 만족하는 정수 $ll$과 $rr$이 주어진다. 해당 쿼리에 대한 답은 $f(A_l,\dots ,A_r)f(A\_l\; ,\; \backslash dots\; ,\; A\_r)$이다. $A_l,\dots ,A_{r}A\_l\; ,\; \backslash dots\; ,\; A\_r$은 $AA$의 $ll$번째 원소부터 $rr$번째 원소까지로 이루어진 부분 수열을 의미한다.

각 쿼리에 대한 답을 구하여라.

입력

첫 번째 줄에 $NN$과 $QQ$가 공백으로 구분되어 주어진다.

두 번째 줄에 $A_1,\dots ,A_{N}A\_1,\; \backslash dots\; ,\; A\_N$이 공백으로 구분되어 주어진다.

이후 $QQ$개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리는 $ll$과 $rr$이 공백으로 구분되어 주어진다.

출력

$QQ$개의 줄에 걸쳐 쿼리들의 답을 입력 순서대로 출력한다.

10 5
5 2 7 3 2 9 6 3 3 5
3 9
1 10
1 8
2 4
8 9

14
27
19
2
0

10 5
2 8 4 9 10 8 5 3 7 7
2 8
1 10
3 3
1 3
8 10

7
11
0
1
0