Horrible Queries

You will be given an array A of n integers. All elements of the array are between 1 and 50 (inclusive). Also, you will be given three integers L, R and k. Consider a subarray AL, AL+1, ...,AR . Now you have to tell how many unique values have at least k occurrences in that subarray.

Input

The first line will contain an integer n (1 < n < 105) denoting the number of elements in the array.

In the next line, there are n numbers A1, A2, ..., An representing the array.

Then you will be given another integer q (1 < q < 105) denoting the number of queries.

Then follows q lines each having three integer numbers L, R and k (1 < L, R, k < n) where L < R.

Output

For each query, print the number of unique values that have at least k occurrences in that subarray.

Sample

Input	Output
15 4 5 3 3 2 40 32 2 1 9 1 10 18 2 3 5 2 4 2 2 12 2 9 12 1 4 10 3 1 15 2	1 3 3 0 3