건초 더미

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

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

첫 번째 줄에는 건초 더미의 설치할 수 있는 위치의 개수 $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)$의 값을 출력한다.