34119번 - 건초 더미 서브태스크

문제

수직선의 위치 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$

서브태스크

힌트