AT_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 翻译