K-query

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

You are given an array $a_1,a_2,\ldots,a_n$. Each query contains $i,j,k$. Count how many values in $a_i,\ldots,a_j$ are strictly greater than $k$.

Input

The first line contains $n$. The second line contains the array. The third line contains $q$. Each of the next $q$ lines contains $i,j,k$.

Output

For each query, print the number of values greater than $k$ in $[i,j]$.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n\le 30000$
• $1\le q\le 200000$
• $1\le a_i,k\le 10^9$
• $1\le i\le j\le n$

Example

Input

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

Output

2
0
3

Explanation

For 2 4 1, the segment is [1,2,3], and two values are greater than $1$.