No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一个长度为 n 的序列，编号为 1∼n ，位置 i 的数为 a_i​

有 m 次询问，每次查询 [l, r] 里小于等于 x 的数的个数。

Format

Input

第一行输入一个整数 n (1≤n≤10⁵)，代表长度为 n 的序列。

第二行输入 n 个整数 a_i(1≤a_i​≤10⁵) ，代表 i 位置的数为 a_i

第三行输入一个整数 m(1≤m≤10⁵) ，代表有 m 次询问。

接下来 m 行输入三个整数 l, r, x(1≤l≤r≤n, 1≤x≤10⁵) ，代表查询区间 [l,r] 里小于等于 x 的数的个数。

Output

对于每次询问，输出一行代表对应的答案。

Samples

5
5 4 1 3 2
2
1 5 3
1 3 4

3
2

Limitation

1s, 1024KiB for each test case.