최악의 기자 3

시간 제한2초메모리 제한256 MB

요약

각 참가자의 느린 정도 D_i가 주어질 때, 시각 T에 좌표 L부터 R까지 구간에 서 있는 참가자 수를 질의마다 구합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 정렬, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

IOI 2018 개막식에서 N명의 참가자가 수직선 위를 행진한다. 모든 참가자는 양의 방향으로 향한다. 시각 0에 앞에서 i번째 참가자(1 ≤ i ≤ N)는 좌표 $-i$ 에 서 있다. 깃발을 든 IOI-chan은 좌표 0에 서 있다.

각 참가자에게는 느림 정도(slowness)라는 값이 있다. i번째 참가자의 느림 정도는 $D_i$ 이다. 참가자들은 다음 규칙을 지킨다.

i번째 참가자와 바로 앞에 있는 사람(참가자 또는 IOI-chan) 사이의 거리가 $D_i + 1$ 이상이면, i번째 참가자는 그 사람과 거리가 1인 위치로 이동한다. 그렇지 않으면 이동하지 않는다.

IOI-chan은 단위 시간마다 양의 방향으로 거리 1만큼 이동한다. 참가자는 위 조건이 만족되는 순간 바로 이동한다.

당신은 개막식을 취재하는 기자다. 원래는 사진을 찍었어야 했지만 식이 진행되는 내내 잠들어 있었다. 그래서 행사장 사진을 찍은 뒤 사진에 사람을 그려 넣기로 했다. 부정행위가 들키지 않도록, 또 그림을 그리는 데 걸리는 시간을 가늠하기 위해 다음 Q개의 값을 알고 싶다.

각 질문 j에 대해, 시각 $T_j$ 에 좌표가 $L_j$ 이상 $R_j$ 이하인 위치에 서 있는 사람의 수를 구하라.

각 참가자의 느림 정도와 Q개의 질문 데이터가 주어질 때, 각 질문의 답을 계산하는 프로그램을 작성하라.

입력

첫째 줄에 참가자 수(IOI-chan 제외) N과 질문 수 Q가 공백으로 구분되어 주어진다.

이어지는 N개의 줄 중 i번째 줄에는 앞에서 i번째 참가자의 느림 정도 $D_i$ 가 주어진다.

이어지는 Q개의 줄 중 j번째 줄에는 세 정수 $T_j$ , $L_j$ , $R_j$ 가 공백으로 구분되어 주어진다.

출력

Q개의 줄을 출력한다. j번째 줄에는 j번째 질문의 답을 출력한다.

제한

$1 \le N \le 500\,000$ .
$1 \le Q \le 500\,000$ .
$1 \le D_i \le 1\,000\,000\,000$ ( $1 \le i \le N$ ).
$1 \le T_j \le 1\,000\,000\,000$ ( $1 \le j \le Q$ ).
$1 \le L_j \le R_j \le 1\,000\,000\,000$ ( $1 \le j \le Q$ ).

예제3

예제 1

입력

예상 출력

예제 2
입력
```
4 2
1
1
1
1
2 1 4
1 3 6
```
예상 출력
```
2
0
```

예제 3

입력

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

예상 출력