Ascending Order

A sequence of positive integers $X_1, \dots, X_M$ of length $M$ is given. Consider making this sequence ascending. The sequence $X_1, \dots, X_M$ is ascending if $X_i \le X_{i+1}$ holds for every $i$ ($1 \le i \le M-1$).

To make $X$ ascending, you may apply the following operation as many times as you want.

• Choose an index $i$ ($1 \le i \le M$) and multiply $X_i$ by $2$.

Let $f(X)$ be the minimum number of operations needed to make $X$ ascending.

You are given a sequence of positive integers $A_1, \dots, A_N$ and $Q$ queries. Each query gives integers $l$ and $r$ with $1 \le l \le r \le N$. The answer to the query is $f(A_l, \dots, A_r)$, where $A_l, \dots, A_r$ is the contiguous subsequence from the $l$-th to the $r$-th element of $A$.

Find the answer to each query.

The first line contains $N$ and $Q$, separated by a space.

The second line contains $A_1, \dots, A_N$, separated by spaces.

Each of the following $Q$ lines contains a query, given as $l$ and $r$, separated by a space.

Print $Q$ lines. The $k$-th line contains the answer to the $k$-th query.

• All given numbers are integers.
• $1 \le N \le 250000$
• $1 \le Q \le 250000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• For every query, $1 \le l \le r \le N$.