송신탑

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

양의 간섭 수치 $\delta$가 주어졌을 때, 송신탑 $i$와 $j$ ($0 \le i < j \le N - 1$)가 서로 통신할 수 있다는 것은 다음 두 조건을 모두 만족하는 중개 송신탑 $k$가 있다는 뜻이다.

• $i < k < j$이다. 즉, 송신탑 $i$는 $k$의 왼쪽에, 송신탑 $j$는 $k$의 오른쪽에 있다.
• 송신탑 $i$와 $j$의 높이는 각각 $H[k] - \delta$ 미터 이하이다.

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

• 팍 뎅클렉은 번호가 $L$부터 $R$까지인 송신탑만 빌릴 수 있다. 양 끝도 포함한다.
• 간섭 수치 $\delta$는 $D$이다.
• 빌린 송신탑들은 어떤 쌍을 고르더라도 서로 통신할 수 있어야 한다.

빌린 두 송신탑이 중개 송신탑 $k$를 이용해 통신할 때, 송신탑 $k$는 빌렸어도 되고 빌리지 않았어도 된다.

• $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$