페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7020
서브태스크

오름차순 4초 1024MB

문제

길이 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를 오름차순으로 만들기 위해, 수열 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번째 원소까지로 이루어진 부분 수열을 의미한다.

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

[제약 조건]

  • 주어지는 모든 수는 정수이다.

  • 1 \le N \le 250,000

  • 1 \le Q \le 250,000

  • 1 \le A_i \le 10^9 (1 \le i \le N)

  • 모든 쿼리에 대해 1 \le l \le r \le N


입력

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

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

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


출력

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


부분문제

번호 점수 조건
#15점

N \le 10,000, Q \le 10,000

#27점

N \le 10,000

#328점

모든 쿼리에 대해 r = N

#410점

A_i \ge A_{i+1} (1 \le i \le N-1)

#55점

A_i \le 2 (1 \le i \le N)

#610점

A_i = 2^{k_i} 를 만족하는 0이상의 정수 k_i가 존재 (1 \le i \le N)

#735점

추가 제약 조건 없음


예제1

입력
105
5273296335
39
110
18
24
89
출력
14
27
19
2
0

예제2

입력
105
28491085377
28
110
33
13
810
출력
7
11
0
1
0

출처

KOI 1차 2024 고3

역링크