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

#8569
서브태스크

건초 더미 2s 1024MB

문제

수직선 위치 0에서 오른쪽 방향으로 정수 크기의 힘을 가진 화살이 발사된다. 각 정수 위치 i (1 \le i \le N)에는 방어력 D_i를 가진 건초 더미를 최대 하나 설치할 수 있다.

화살이 건초 더미에 부딪쳤을 때 화살의 힘이 방어력보다 작거나 같으면, 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 힘이 방어력 D_i만큼 감소한 뒤 건초 더미를 관통해 계속 날아간다.

두 정수 X, P에 대하여 f(X,P)의 값을 "힘이 P인 화살이 위치 X에서 멈추거나 위치 X보다 왼쪽에서 멈추도록 하기 위해 설치해야 하는 건초 더미의 최소 개수"라고 정의하자. 만약 어떠한 설치 방법으로도 화살을 멈추게 할 수 있는 방법이 없다면 f(X,P)=-1로 정의한다.

Q개의 정수 쌍 (X_j, P_j) (1 \le j \le Q)에 대해 각각 f(X_j, P_j)의 값을 구하는 프로그램을 작성하라.

[제약 조건]

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

  • 1 \le N, Q\le 300\,000

  • 1\le i \le N인 모든 i에 대하여 1 \le D_i \le 10^9

  • 1 \le j \le Q인 모든 j에 대하여 1 \le X_j \le N

  • 1 \le j \le Q인 모든 j에 대하여 1 \le P_j \le 10^9


입력

첫 번째 줄에는 건초 더미의 설치할 수 있는 위치의 개수 N과 발사되는 화살의 횟수 Q가 공백을 사이에 두고 주어진다.

두 번째 줄에는 위치 i (1 \le i \le N)에 놓을 수 있는 건초 더미의 방어력 D_1, D_2, \cdots, D_N이 공백을 사이에 두고 주어진다.

세 번째 줄부터 Q개의 줄에 걸쳐 Q개의 정수 쌍이 주어진다. 이 중 j (1 \le j \le Q)번째 줄에는 X_j와 P_j가 공백을 사이에 두고 주어진다.


출력

Q개의 줄을 출력한다. 이 중 j (1 \le j \le Q)번째 줄에는 f(X_j, P_j)의 값을 출력한다.


부분문제

번호 점수 조건
#16점

N, Q \le 18

#216점

N,Q \le 5\,000

#318점

1 \le i \le N인 모든 i에 대하여 D_i \le 300

#432점

1 \le i \le N인 모든 i에 대하여 D_i \le D_{i+1}

#528점

N=Q, 1 \le j \le Q인 모든 j에 대하여 X_j = j, P_1 = P_2 = \cdots = P_Q

#616점

1 \le j \le Q인 모든 j에 대하여 X_j = N

#712점

1 \le i \lt j \le N인 모든 i,j에 대하여 D_i \neq D_j

#822점

추가 제약 사항 없음.


예제 #1

5 6
2 5 6 1 12
1 1
5 14
2 8
3 7
4 14
5 1
1
2
-1
2
4
1

예제 #2

5 5
3 6 1 1 10
1 10
2 10
3 10
4 10
5 10
-1
-1
3
3
1


출처

2025 KOI 1차 중3
로그인해야 코드를 작성할 수 있어요.