長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。以下のクエリを処理するプログラムを作成せよ。
i j k: 部分列 $A_i, A_{i+1}, \ldots, A_j$ の中で $k$ より大きい要素の個数を出力する。
入力
1行目には数列のサイズ $N$ が与えられる。$(1 \le N \le 100{,}000)$
2行目には $A_1, A_2, \ldots, A_N$ が与えられる。$(1 \le A_i \le 10^9)$
3行目にはクエリの個数 $M$ が与えられる。$(1 \le M \le 100{,}000)$
続く $M$ 行にはそれぞれクエリ $i, j, k$ が与えられる。$(1 \le i \le j \le N, 1 \le k \le 10^9)$
出力
各クエリに対して、答えを1行ずつ出力せよ。
入出力例
入力 1
5 5 1 2 3 4 3 2 4 1 4 4 4 1 5 2
出力 1
2 0 3