오름차순

길이 $M$인 양의 정수열 $X_1, \dots, X_M$이 주어진다. 이 수열을 오름차순으로 만들어 보자. 수열 $X_1, \dots, X_M$이 오름차순이라는 것은 각 $i$ ($1 \le i \le M-1$)에 대해 $X_i \le X_{i+1}$이 성립한다는 뜻이다.

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

• 어떤 $i$ ($1 \le i \le M$)를 골라 $X_i$에 $2$를 곱한다.

$X$를 오름차순으로 만드는 데 필요한 연산의 최소 횟수를 $f(X)$라고 하자.

길이 $N$의 양의 정수열 $A_1, \dots, A_N$과 쿼리 $Q$개가 주어진다. 각 쿼리는 $1 \le l \le r \le 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 \le N \le 250000$
• $1 \le Q \le 250000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• 모든 쿼리에 대해 $1 \le l \le r \le N$