Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Horrible Queries

Limits 1s, 512 MB

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

InputOutput
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

Discussion

Statistics


73% Solution Ratio

fsshakkhorEarliest, Nov '17

mdvirusFastest, 0.0s

maf_uuLightest, 655 kB

MuezzaShortest, 372B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.