#P18028. Find "rururutata"

Find "rururutata"

Find "rururutata"

若一个序列可以写为 r+r+r+t+tr+r+r+t+t,其中 ++ 表示拼接,r,tr,t 都是非空序列,则称它为 rururutata 型序列。rr 和 tt 可以相同,也可以不同。

给定长度为 NN 的整数序列 SS。对于每个查询 L,RL,R,判断 (SL,SL+1,…,SR)(S_L,S_{L+1},\ldots,S_R) 中是否存在一个连续子数组是 rururutata 型序列。

输入格式

第一行一个整数 NN。第二行 NN 个整数 S1,…,SNS_1,\ldots,S_N。

第三行一个整数 QQ。接下来 QQ 行,每行两个整数 L,RL,R,表示一次查询。

输出格式

输出 QQ 行。对应查询存在所需子数组时输出 Yes,否则输出 No。

数据范围

1≤N,Q≤5×1051\le N,Q\le5\times10^5,1≤Si≤N1\le S_i\le N,1≤L≤R≤N1\le L\le R\le N。所有输入均为整数。

样例说明

查询 [1,5][1,5] 对应 (3,3,3,2,2)(3,3,3,2,2),可取 r=(3),t=(2)r=(3),t=(2)。查询 [4,12][4,12] 中的子数组 (2,2,2,4,3,4,3)(2,2,2,4,3,4,3) 可取 r=(2),t=(4,3)r=(2),t=(4,3)。并不要求整个查询区间恰好是这种序列。

样例 1

输入:

17
3 3 3 2 2 2 4 3 4 3 4 3 2 2 2 2 2
5
1 5
4 12
2 6
8 15
13 17

输出:

Yes
Yes
No
No
Yes