AT_1_stpc2025_1_e.Max Twice Subsequences

给定一个长度为 $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$ 的非空子序列，且在 $B$ 中至少出现两次，形式化地说，存在正整数 $k$ 和两个下标序列 $(i_1,i_2,\dots,i_k),(j_1,j_2,\dots,j_k)$ 满足以下所有条件，则称 $C$ 为好序列：

• $1\le i_1 < i_2 < \dots < i_k \le |B|$
• $1\le j_1 < j_2 < \dots < 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$。

输入格式如下：

$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

解释第 $1$ 个查询。对于 $B=(3,2,1,2,3)$，作为非空子序列出现至少两次的所有子序列中，字典序最大的为 $(3,2,3)$。可以取两组下标分别为 $(1,2,5),(1,4,5)$。

第 $2$ 个查询，$B=(3,2,1)$，没有非空子序列出现两次或以上。

第 $3$ 个查询，$B=(2,1,2)$，字典序最大的为 $(2)$。

第 $4$ 个查询，$B=(2,1,2,3)$，字典序最大的为 $(2,3)$。

数据范围

• 输入均为整数
• $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)$

由 ChatGPT 5 翻译