题目描述

给定有 $n$ 个元素的数组 a， 请有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是指在子数组中出现 k 次或以上次的元素。

这里的子数组是指 a 中连续的一段。

输入格式

第一行一个整数 $n$，表示 a 的长度；

第二行 $n$ 个空格隔开的整数，表示 a 中的各个元素。

第三行 一个 整数 $q$，表示询问的次数；

接下来的 $q$ 行，每行空格隔开三个的整数 $L, R, k$，表示寻找 $[L, R]$ 范围内出现 k 次或以上次的元素。

输出格式

共 $q$ 行，至少出现 k 次的数，如果不存在这样的元素则返回 -1。

样例

示例 1：

6
1 1 2 2 1 1
3
1 6 4
1 4 3
3 4 2

1
-1
2

数据规模及限制

• $1 \le n \le 2 \times 10^4$
• $1 \le a_i \le2 \times 10^4$
• $1 \le L \le R \le n$
• $k \le R - L + 1$
• $2 \times k > R - L + 1$
• $1 \le q \le 10^4$