건초 더미

문제

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

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

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

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

입력

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

두 번째 줄에는 위치 $ii$ (1 &le; i &le; N)에 놓을 수 있는 건초 더미의 방어력 $D_1,D_2,\cdots ,D_{N}D\_1\; ,\; D\_2\; ,\; \backslash cdots,\; D\_N$이 공백을 사이에 두고 주어진다.

세 번째 줄부터 $QQ$개의 줄에 걸쳐 $QQ$개의 정수 쌍이 주어진다. 이 중 $jj$ (1 &le; j &le; Q)번째 줄에는 $X_{j}X\_j$와 $P_{j}P\_j$가 공백을 사이에 두고 주어진다.

출력

$QQ$개의 줄을 출력한다. 이 중 $jj$ (1 &le; j &le; Q)번째 줄에는 $f(X_j,P_j)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