問題文

数列 $A$、正整数 $k$ に対し、$f(k)$ を以下のように定義します。

• $f(k) :=$ 数列 $A$ を $1$ つ以上の空ではない連続部分列に分割する $2^{(|A|-1)}$ 通りの方法のうち、次の条件を満たすものの個数

すべての連続部分列について、その区間が $k$ 種類以下の値からなる。（2024/4/19 21:34修正）

$f(k) \leqq S$ を満たす $k$ の最大値か存在するか判定し、存在するならそのときの $k$ の最大値を答えてください。

長さ $N$ の数列 $X$ とクエリが $Q$ 個与えられます。$(X_l, X_{l+1}, ..., X_r) $ を数列 $A$ と見なしたとき、以上の問題にそれぞれ答えてください。

入力

$N$
$X_{1}\ X_{2}\ \cdots\ X_{N}$  
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

• 入力はすべて整数である。
• $1 \leqq N \leqq 10^6$
• $0 \leqq X_i \leqq N$
• $1 \leqq Q \leqq 10^4$
• $1 \leqq l \leqq r \leqq N$
• $1 \leqq S \leqq 2^{60}$

$i$ 番目のクエリ $\text{query}_i$ では 整数組 $(l, r , S)$ が以下の形式で与えられます。

$l\ r\ S$

出力

$\text{query}_i$ の答えを $i$ 行目 $(1 \leqq i \leqq Q)$に出力してください。 具体的には

• $f(k) \leqq S$ を満たす正整数 $k$ の最大値が存在する場合は、そのときの $k$ の値
• $f(k) \leqq S$ を満たす正整数 $k$ が存在しない場合は、0
• $f(k) \leqq S$ を満たす正整数 $k$ は存在するが、その最大値が存在しない場合、-1

サンプル

7
1 2 3 2 1 1 2
3
1 4 7
2 5 100
3 7 1

2
-1
0

サンプル

3
0 0 0
4
1 3 1
1 3 2
1 3 3
1 3 4

0
0
0
-1