길이가 \(N\)인 수열 \(A_1, A_2, \dots, A_N\)이 주어진다. 이때 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j k: \(A_i, A_{i+1}, \dots, A_j\) 중 \(k\)보다 큰 원소의 개수를 출력한다.

입력

첫 번째 줄에 수열의 크기 \(N\)이 주어진다.

두 번째 줄에는 수열의 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

세 번째 줄에는 쿼리의 개수 \(Q\)가 주어진다.

네 번째 줄부터 \(Q\)개의 줄에 걸쳐 각 쿼리를 나타내는 세 정수 \(i, j, k\)가 공백으로 구분되어 주어진다.

\((1 \le N \le 100,000)\)

\((1 \le Q \le 100,000)\)

\((1 \le A_i \le 10^9)\)

\((1 \le i \le j \le N)\)

\((0 \le k \le 10^9)\)

출력

각 쿼리의 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

2
3
0