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

#8569 upload 159 done 44 how_to_reg 40 call_split 서브태스크

건초 더미 timer 2s memory 1024MB

#8569
서브태스크

건초 더미 2s 1024MB