60004 건초 더미 Gold II

문제

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

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

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

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

입력

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

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

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

출력

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

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N, Q ≤ 300\, 000$
• $1 ≤ i ≤ N$인 모든 $i$에 대하여 $1 ≤ D_i ≤ 10^9$
• $1 ≤ j ≤ Q$인 모든 $j$에 대하여 $1 ≤ X_j ≤ N$
• $1 ≤ j ≤ Q$인 모든 $j$에 대하여 $1 ≤ P_j ≤ 10^9$

서브태스크

번호	배점	제한
1	6	$N, Q ≤ 18$
2	16	$N, Q ≤ 5\, 000$
3	18	$1 ≤ i ≤ N$인 모든 $i$에 대하여 $D_i ≤ 300$
4	32	$1 ≤ i < N$인 모든 $i$에 대하여 $D_i ≤ D_{i+1}$
5	28	$N = Q$, $1 ≤ j ≤ Q$인 모든 $j$에 대하여 $X_j = j$, $P_1 = P_2 = \cdots = P_Q$
6	16	$1 ≤ j ≤ Q$인 모든 $j$에 대하여 $X_j = N$
7	12	$1 ≤ i < j ≤ N$인 모든 $i$, $j$에 대하여 $D_i ≠ D_j$
8	22	추가 제약 사항 없음.

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

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

-1
-1
3
3
1