Placeholder

#7020
서브태스크

오름차순 4초 1024MB

문제

길이 MM인 양의 정수열 X1,…,XMX_1, \dots, X_M이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자.

수열 X1,…,XMX_1, \dots, X_M이 오름차순이라는 것은, 각 ii (1≤i≤M−1)(1 \le i \le M-1)에 대해 Xi≤Xi+1X_i \le X_{i+1}이라는 것이다.


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

  • 어떤 ii (1≤i≤M)(1 \le i \le M)에 대해 XiX_i에 22를 곱한다.

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

길이 NN의 양의 정수열 A1,…,ANA_1, \dots, A_N과 쿼리 QQ개가 주어진다.

각 쿼리에는 1≤l≤r≤N1 \le l \le r \le N을 만족하는 정수 ll과 rr이 주어진다. 해당 쿼리에 대한 답은 f(Al,…,Ar)f(A_l, \dots, A_r)이다.

Al,…,ArA_l, \dots, A_r은 AA의 ll번째 원소부터 rr번째 원소까지로 이루어진 부분 수열을 의미한다.


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


[제약 조건]

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

  • 1≤N≤250,0001 \le N \le 250,000

  • 1≤Q≤250,0001 \le Q \le 250,000

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

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


입력

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

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

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


출력

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


부분문제

번호 점수 조건
#15점

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

#27점

N≤10,000N \le 10,000

#328점

모든 쿼리에 대해 r=Nr = N

#410점

Ai≥Ai+1A_i \ge A_{i+1} (1≤i≤N−1)(1 \le i \le N-1)

#55점

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

#610점

Ai=2kiA_i = 2^{k_i}를 만족하는 00이상의 정수 kik_i가 존재 (1≤i≤N)(1 \le i \le N)

#735점

추가 제약 조건 없음


예제1

입력
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

예제2

입력
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

출처

KOI 1차 2024 고3


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.
오름차순 - JUNGOL