Description

You are given a sequence of length $n$, with $m$ query operations.

Each query gives parameters $l,r,b$. You need to output the maximum $x$ such that there exists an $a$ with $0\leq a<b$ satisfying that $a,a+b,a+2b,\ldots,a+(x-1)b$ have all appeared at least once within the interval $[l,r]$.

If no number in $[0,b-1]$ exists, output $0$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing the sequence.

The third line contains an integer $m$.

Then follow $m$ lines, each containing three integers $l,r,b$, representing one query operation.

Output Format

For each query operation, output one line with one integer representing the answer.

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.

For $30\%$ of the testdata, all numbers that appear are within $[0,1000]$.

For another $30\%$ of the testdata, $b \leq 1000$.

For $100\%$ of the testdata, all numbers that appear are within $[0,10^5]$.

Translated by ChatGPT 5