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) $ が $ 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 $ を答えてください。 **ただし、すべてのクエリに渡る** $ R_i-L_i+1 $ **の総和は** $ 10^7 $ **以下であることが保証されます。**

入力は以下の形式で与えられる。 > $ 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}) $ を与えたときの答えを出力せよ。

### Sample Explanation 1 $ 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) $ です。 ### Constraints - 入力はすべて整数 - $ 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 $