← 返回题目列表

AtCoder · pakencamp_2025_day3_e

E. 查找“rururutata”

中文机器翻译题面 查看原题

配点 : 100 点

問題文

Lululutata 序列的,不为空 使用数列 r,t , 将其定义为可以表示为r+r+r+t+t 的数字序列。 您将收到

长度 N 的正整数序列 A=(A_1,A_2,\dots,A_N) 。Q 查询,因此请按顺序处理它们。

每个查询的整数 给出了 L,R ,所以 对于(A_L,A_{L+1},\dots,A_{R}) 的连续子序列 判断Lululutata 序列是否存在。

制約

  • 1\leq N\leq 5\times 10^5
  • 1\leq A_i\leq N (1\leq i\leq N)
  • 1\leq Q\leq 5\times 10^5
  • 1\leq L\leq R\leq N
  • 所有输入均为整数

入力

N
A_1 A_2 \dots A_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

每个查询均按以下格式给出。 输出

L R

出力

Q 行。 对于第

i 行中,i 个查询, 如果Lululutata 序列存在 Yes 如果没有 对于第 No 。


入力例 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

出力例 1

Yes
Yes
No
No
Yes

1 个查询,(S_1,S_2,S_3,S_4,S_5)=(3,3,3,2,2) 是 仅由Lululutata 序列。r=(3),t=(2) 满足条件。

2 个查询, 如果(S_4,S_5,\dots,S_{12}) 的连续子序列 (S_4,S_5,\dots,S_{10})=(2,2,2,4,3,4,3) 是 仅由Lululutata 序列。r=(2),t=(4,3) 满足条件。

3 个查询, 如果(3,3,2,2,2) 是 仅由Lululutata 序列并且明显更短。Lululutata 序列也不包括在内。 请注意,

4 个查询, 如果(3,3,3,2,2) 不是连续的子序列。 请注意,

5 个查询, 如果r=t 也是可以接受的。