Disordered Data Detection

Time Limit : 5 sec, Memory Limit : 131072 KB

F: Disordered Data Detection / 異常検知

物語

宮守あかねは武蔵野ソフトウェアに務めるエンジニアである.今日は顧客から受けた不具合報告に頭を悩ませている.「変な話,この前作ってもらったソフトの挙動がぷるんぷるんしてるんでぇ,そちらでチェックしてもらえますか?保守するのもおたくらの仕事でしょ?」いつも無理難題ばかり押し付けてくるこの顧客だが,今回ばかりはこちらに非がある.なぜなら,いつも適当な仕事ばかりのジローがテストに通っていないコードをそのまま放置して製品に組み込んだことを告白したからである.普通の人間ならジローに殴りかかりそうなものだが,もはやいつものことだ,あかねは怒りを通り越し,すでに悟りを開きつつある.なにはともあれ,バグを取り除かなければならない.まずはデータログを解析し,異常が出ている箇所を検知することでバグの原因を探ろう.

今,D 日分のログがあり,各データは1つの整数である.l 日目から r 日目までのデータについて,l 日目のデータと r 日目のデータの間に収まらず,大きくかけ離れたデータは異常の可能性が高いと考えられる.よって,指定された期間を入力とし,上記のような外れ値を検知するコードを書くことにした.

顧客が提示したデバッグ期限は3時間後.万策尽きたかのような状況だが,あかねは何度もこのような状況を乗り越えてきた.お気に入りのドーナツを頬張り気合を入れて,どんどんデバッグ,どーんと行こう!

問題

長さ D の整数列 x_1, . . . , x_D がある.この数列に対し Q 回のクエリが与えられる.i 番目のクエリは3つの整数 l_i, r_i, e_i からなる.i 番目のクエリに対し,a_i = min\{x_{l_i},x_{r_i}\}, b_i = max\{x_{l_i},x_{r_i}\} としたとき,x_j < a_i − e_i もしくは b_i+e_i < x_j を満たすような l_i ≤ j ≤ r_i の個数を答えよ.

入力形式

入力は以下の形式からなる.

 D
 x_1 x_2  . . .  x_D
 Q
 l_1 r_1 e_1
  . . . 
 l_Q r_Q e_Q

入力の1行目は数列の長さを表す1つの整数 D (1 ≤ D ≤ 100{,}000) からなる.2行目では,数列 X を表す D 個の整数がそれぞれ空白1つを区切りとして与えられる.i 番目の整数 x_i−10^8 ≤ x_i ≤ 10^8 を満たす.

3行目はクエリの個数を表す1つの整数 Q (1≤ Q ≤ 100{,}000) からなる.続く Q 行のうち j 番目の行では,j 番目のクエリを表す3つの整数 l_j, r_j, e_j が空白1つを区切りとして与えられる.j 番目のクエリについて,1 ≤ l_j ≤ r_j ≤ D, 0 ≤ e_j ≤ 10^8 を満たす.

出力形式

Q 個のクエリに対する答えを,クエリが与えられた順にそれぞれ1行ごとに出力せよ.

入力例1

7
4 1 10 5 7 7 3
5
2 5 0
3 6 1
3 6 2
1 7 2
1 7 5

出力例1

1
1
0
3
1

入力例2

9
8 3 0 2 5 2 5 2 1
3
1 3 5
2 5 0
3 9 0

出力例2

0
2
5

入力例3

9
10 10 10 7 2 10 10 1 5
13
3 3 6
3 4 5
3 5 4
3 6 3
3 7 2
3 8 1
3 9 0
4 9 1
5 9 2
6 9 3
7 9 4
8 9 5
9 9 6

出力例3

0
0
0
1
2
0
2
4
2
1
0
0
0

Source: Ritsumeikan University Programming Camp 2015 , Problem set from Hokkaido University teams, Shiga, Japan, 2015-03-16