配点 : 100 点
問題文
长度 小于或等于 N 的正整数序列 给出了 A=(A_1,A_2,\dots, A_N) 。 对于
Q 询问。i 查询中的整数 给出了 L_i,R_i ,所以对于下一个问题 找到给出的答案 B = (A_{L_i},A_{L_i+1},\dots ,A_{R_i}) 。
正整数列 B=(B_1,B_2,\dots, B_{|B|}) 。正整数序列 作为 C=(C_1,C_2,\dots, C_k) 是 在 B 的非空子序列 当出现超过 2 次时,形式上为正整数 k 和 按字典顺序比较 2 两个下标的序列 当 (i_1,i_2,\dots ,i_k),(j_1,j_2,\dots ,j_k) 存在且满足以下所有条件时, C 该值应乘以好专栏。
- 1\le i_1\lt i_2\lt \dots \lt i_k\le |B|
- 1\le j_1\lt j_2\lt \dots \lt j_k\le |B|
- p=1,2,\dots ,k 反对 B_{i_p}=B_{j_p}=C_p 成立。
- 是 小于或等于 p\ (1\le p\le k) 存在 i_p\neq j_p 成立。
确定是否存在好列,如果存在,则使用字典顺序最大的好列之一。 滚动哈希 。然而,正整数序列 将其定义为 a=(a_1,\dots, a_n) 可以得到第 滚动哈希 是 您也可以写 \displaystyle \left(\sum_{i=1}^{n}a_i 3^{i-1}\right)\bmod 998244353 。如果它不存在 请回答 -1 。
制約
- 所有输入均为整数
- 1\le N,Q\le 3\times 10^5
- 1\le A_i\le N\ (1\le i\le N)
- 1\le L_i\le R_i\le N\ (1\le i\le Q)
入力
输入按以下格式给出。
N Q A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
Q 行。 i=1,2,\dots, Q 关于 i 线路有问题。 B = (A_{L_i},A_{L_i+1},\dots,A_{R_i}) 。 我们来谈谈第
入力例 1
5 4 3 2 1 2 3 1 5 1 3 2 4 2 5
出力例 1
36 -1 2 11
1 个查询。 B=(3,2,1,2,3) 的非空子序列 当出现超过 2 字典顺序上出现多次的最大的一个是 (3,2,3) 。给这个 2 作为两个下标的序列, 您可以采取 (1,2,5),(1,4,5) 。
2 查询中 给定 B=(3,2,1) 作为非空子序列 任何内容出现的次数不得超过 2 次。
3 查询中 给定 B=(2,1,2) 作为非空子序列 任何内容出现的次数不得超过 2 字典顺序上出现多次的最大的一个是 (2) 。
4 查询中 给定 B=(2,1,2,3) 作为非空子序列 任何内容出现的次数不得超过 2 字典顺序上出现多次的最大的一个是 (2,3) 。
入力例 2
5 1 3 2 1 4 1 1 5
出力例 2
18
入力例 3
10 10 1 4 5 2 5 3 4 2 5 4 1 10 1 9 2 10 1 8 2 9 3 10 1 7 2 8 3 9 4 10
出力例 3
56 20 56 35 20 56 17 35 20 17