60022 오름차순

문제

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

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

• 어떤 $i$ ($1 ≤ i ≤ M$)에 대해 $X_i$에 $2$를 곱한다.

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

길이 $N$의 양의 정수열 $A_1, \dots , A_N$과 쿼리 $Q$개가 주어진다. 각 쿼리에는 $1 ≤ l ≤ r ≤ N$을 만족하는 정수 $l$과 $r$이 주어진다. 해당 쿼리에 대한 답은 $f(A_l , \dots , A_r)$이다. $A_l , \dots , A_r$은 $A$의 $l$번째 원소부터 $r$번째 원소까지로 이루어진 부분 수열을 의미한다.

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

입력

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

두 번째 줄에 $A_1, \dots , A_N$이 공백으로 구분되어 주어진다.

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

출력

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

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 250\, 000$
• $1 ≤ Q ≤ 250\, 000$
• $1 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ N$)
• 모든 쿼리에 대해 $1 ≤ l ≤ r ≤ N$

서브태스크

1	5	$N ≤ 10\, 000$, $Q ≤ 10\, 000$
2	7	$N ≤ 10\, 000$
3	28	모든 쿼리에 대해 $r = N$
4	10	$A_i ≥ A_{i+1}$ ($1 ≤ i ≤ N - 1$)
5	5	$A_i ≤ 2$ ($1 ≤ i ≤ N$)
6	10	$A_i = 2^{k_i}$를 만족하는 $0$ 이상의 정수 $k_i$가 존재 ($1 ≤ i ≤ N$)
7	35	추가 제약 조건 없음

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