Description

给你一个长为 $n$ 的序列，有 $m$ 次查询操作。

每次查询操作给定参数 $l,r,b$，需输出最大的 $x$，使得存在一个 $a$，满足 $0\leq a<b$，使得 $a,a+b,a+2b,\ldots,a+(x-1)b$ 都在区间 $[l,r]$ 内至少出现过一次。

如果不存在 $[0,b-1]$ 内的数，则输出 $0$。

Input Format

第一行一个整数 $n$。

第二行 $n$ 个整数表示这个序列。

第三行一个整数 $m$。

之后 $m$ 行，每行三个整数 $l,r,b$，表示一次查询操作。

Output Format

对于每个查询操作，输出一行一个整数表示答案。

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

0
2
0

Hint

Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078&Forever_Pursuit

对于 $30\%$ 的数据，所有出现过的数在 $[0,1000]$ 之间。

对于另外 $30\%$ 的数据，$b \leq 1000$。

对于 $100\%$ 的数据，所有出现过的数在 $[0,10^5]$ 之间。