题目描述

本题和 BZOJ 某权限题似乎撞了，但是数据范围比原题要大，因此怀疑做法不同，应该可以作为新题吧
由于没有联系上出题人（貌似叫 nzhtl1477？），还没有和原题出题人沟通过

校园的小路旁，郁金香在盛开。
小 A 看着道旁的郁金香，感觉这些郁金香五颜六色，红的，紫的，黄的，白的，粉的……非常好看。
看着这些郁金香，小 A 突然冒出来一个问题：某一段连续的郁金香中出现次数第 $k$ 多的颜色是哪一种？
小 A 感觉这道题非常的有趣，就想把这道题出出来坑一坑做题的，但是小 A 还要去吃香爆脆，所以他就把写标程的任务交给你了。

我们可以把道旁的郁金香看作是一个线型结构，位置编号为 $1 \sim n$，每个位置上都恰好有一朵郁金香。简单起见，我们把郁金香的颜色都用 $1 \sim n$ 的整数表示，同时如果有不止一种颜色的出现次数相同，则认为数值较小的颜色出现次数较多。

输入格式

第一行一个整数 $n$，分别表示郁金香总数。
第二行有 $n$ 个整数，表示每株郁金香的颜色。
第三行一个整数 $m$，表示询问次数。
以下 $m$ 行，每行三个整数 $l,r,k$，表示询问区间 $[l,r]$ 中出现次数第 $k$ 多的颜色。

输出格式

对于每个询问，单独一行输出一个整数表示答案。如果出现次数第 $k$ 多的颜色不存在，输出 $0$。

样例

input

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

output

1
2
1
0
3

数据范围与提示

$n,m\leqslant 10^5$