AT_stpc2025_2_e Max Twice Subsequences (Easy)

给定一个长度为 $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)$ 满足 $C$ 作为 $B$ 的非空子序列出现至少两次（形式上，存在正整数 $k$ 和两组下标序列 $(i_1,i_2,\dots,i_k),(j_1,j_2,\dots,j_k)$ 满足以下所有条件，使得 $C$ 被称为**好序列**）： > > - $1\le i_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$ 行输出对应 $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)$ - $\sum_{i=1}^{Q}(R_i-L_i+1)\le 10^7$ 由 ChatGPT 5 翻译