송신탑

자카르타에는 $N$개의 송신탑이 있다. 송신탑들은 일직선상에 위치하며 왼쪽에서 오른쪽으로 $0$부터 $N - 1$까지 번호가 붙어 있다. $0 \le i \le N - 1$인 각 $i$에 대해 송신탑 $i$의 높이는 $H[i]$미터이다. 송신탑들의 높이는 모두 다르다.

어떤 양의 간섭 수치 $\delta$에 대해 한 쌍의 송신탑 $i$와 $j$ ($0 \le i < j \le N - 1$)가 서로 통신할 수 있다는 것은 다음을 모두 만족하는 중개 송신탑 $k$가 존재한다는 것을 의미한다.

• 송신탑 $i$는 송신탑 $k$의 왼쪽에 위치하고 송신탑 $j$는 송신탑 $k$의 오른쪽에 위치한다. 즉, $i < k < j$이다.
• 송신탑 $i$와 $j$의 높이는 모두 최대 $H[k] - \delta$미터이다.

팍 뎅클렉은 자신의 새로운 송신 네트워크를 위해 몇 개의 송신탑을 빌리려고 한다. 당신은 다음과 같은 팍 뎅클렉의 질문 $Q$개에 대해 답변해야 한다. 파라미터 $L$, $R$과 $D$ ($0 \le L \le R \le N - 1$이고 $D > 0$)가 주어지면 팍 뎅클렉이 빌릴 수 있는 송신탑의 최대 개수는 몇 개인가? 단, 다음을 가정한다.

• 팍 뎅클렉은 번호 $L$과 $R$ 사이 ($L$과 $R$ 포함)의 송신탑만 빌릴 수 있고,
• 간섭 수치 $\delta$는 $D$이고,
• 팍 뎅클렉이 빌리는 송신탑들은 어떤 쌍을 선택하든지 서로 통신할 수 있어야 한다.

참고로 빌린 두 송신탑이 중개 송신탑 $k$를 이용하여 통신할 수 있을 때 송신탑 $k$는 빌렸어도 되고 빌리지 않았어도 된다.

구현 세부사항

다음 함수들을 구현해야 한다.

void init(int N, int[] H)

• $N$: 송신탑의 개수.
• $H$: 송신탑의 높이를 나타내는 길이 $N$인 배열.
• 이 함수는 최초에 한 번만 호출된다. 이후에 아래에 설명된 max_towers 호출이 이어진다.

int max_towers(int L, int R, int D)

• $L$, $R$: 송신탑 범위의 경계.
• $D$: 간섭 수치 $\delta$.
• 이 함수는 팍 뎅클렉이 빌릴 수 있는 송신탑의 범위가 $L$과 $R$ 사이 ($L$과 $R$ 포함)로 한정되고 간섭 수치 $\delta$가 $D$일 때 그가 빌릴 수 있는 송신탑의 최대 개수를 리턴해야 한다.
• 이 함수는 정확히 $Q$번 호출된다.

예제

다음 호출들을 생각해보자.

init(7, [10, 20, 60, 40, 50, 30, 70])

max_towers(1, 5, 10)

팍 뎅클렉은 송신탑 $1$, $3$, 그리고 $5$를 빌릴 수 있다. 아래 그림에서 색칠된 사다리꼴이 빌린 송신탑을 나타낸다.

$40 \le 50 - 10$이고 $30 \le 50 - 10$이므로 송신탑 $3$과 $5$는 송신탑 $4$를 중개 송신탑으로 이용해서 서로 통신할 수 있다. 송신탑 $1$과 $3$은 중개 송신탑 $2$를 이용하여 서로 통신할 수 있다. 송신탑 $1$과 $5$는 중개 송신탑 $3$을 이용하여 서로 통신할 수 있다. $3$개보다 더 많은 송신탑을 빌릴 수 있는 방법이 없으므로 함수는 $3$을 리턴해야 한다.

max_towers(2, 2, 100)

범위에 포함되는 송신탑이 $1$개밖에 없으므로 팍 뎅클렉은 오직 $1$개의 송신탑만 빌릴 수 있다. 따라서 함수는 $1$을 리턴해야 한다.

max_towers(0, 6, 17)

팍 뎅클렉은 송신탑 $1$과 $3$을 빌릴 수 있다. $20 \le 60 - 17$이고 $40 \le 60 - 17$이므로 송신탑 $1$과 $3$은 중개 송신탑 $2$를 이용하여 서로 통신할 수 있다. $2$개보다 더 많은 송신탑을 빌릴 수 있는 방법이 없으므로 함수는 $2$를 리턴해야 한다.

제약 조건

• $1 \le N \le 100\;000$
• $1 \le Q \le 100\;000$
• $1 \le H[i] \le 10^9$ ($0 \le i \le N - 1$)
• $H[i] \ne H[j]$ ($0 \le i < j \le N - 1$)
• $0 \le L \le R \le N - 1$
• $1 \le D \le 10^9$

서브태스크

1. (4점) 다음을 모두 만족하는 송신탑 $k$ ($0 \le k \le N - 1$)가 존재한다.
   • $0 \le i \le k - 1$인 모든 $i$에 대해 $H[i] < H[i + 1]$이고,
   • $k \le i \le N - 2$인 모든 $i$에 대해 $H[i] > H[i + 1]$이다.
2. (11점) $Q = 1$, $N \le 2000$
3. (12점) $Q = 1$
4. (14점) $D = 1$
5. (17점) $L = 0$, $R = N - 1$
6. (19점) 모든 max_towers 호출에 대해 $D$ 값이 동일하다.
7. (23점) 추가적인 제한이 없다.

• line $1$: $N \; Q$
• line $2$: $H[0] \; H[1] \; \ldots \; H[N - 1]$
• line $3 + j$ ($0 \le j \le Q - 1$): $L \; R \; D$ ($j$번째 질문을 위한 $L$, $R$, $D$임)

샘플 그레이더는 다음 형식으로 답을 출력한다.

• line $1 + j$ ($0 \le j \le Q - 1$): $j$번째 max_towers 호출의 리턴 값

샘플 그레이더의 입력 양식은 다음과 같다.