60004 건초 더미 Gold II

문제

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

화살이 건초 더미에 부딪혔을 때, 화살의 힘이 방어력 이하이면 즉시 멈추고, 화살의 힘이 방어력보다 크면 힘이 방어력만큼 감소하고 관통한다.

두 정수 X, P에 대하여 f(X, P)를 “힘이 P인 화살이 위치 X에서 멈추거나 위치 X보다 왼쪽에서 멈추도록 하기 위해 설치해야 하는 건초 더미의 최소 개수”로 정의한다. 불가능하면 f(X, P) = -1이다.

Q개의 쿼리가 주어질 때, 각 쿼리에 대해 f(X_j, P_j)를 구하시오.

입력

첫째 줄에 N, Q가 주어진다. (1 ≤ N, Q ≤ 300,000)

둘째 줄에 D_1, D_2, …, D_N이 주어진다. (1 ≤ D_i ≤ 10^9)

다음 Q개의 줄에 X_j, P_j가 주어진다. (1 ≤ X_j ≤ N, 1 ≤ P_j ≤ 10^9)

출력

Q개의 줄에 각각 f(X_j, P_j)를 출력한다.

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