#P17931. Max Twice Subsequences

Max Twice Subsequences

Max Twice Subsequences

给定长度为 NN 的正整数序列 AA,回答 QQ 个独立的区间询问。每个询问给定 L,RL,R,令 B=(AL,AL+1,…,AR)B=(A_L,A_{L+1},\ldots,A_R)。

若非空序列 C=(C1,…,Ck)C=(C_1,\ldots,C_k) 作为 BB 的子序列至少出现两次,则称它为合法序列。严格地说,必须存在两组下标

$$1\le i_1<\cdots<i_k\le |B|,\qquad1\le j_1<\cdots<j_k\le |B|,$$

满足对所有 pp 都有 Bip=Bjp=CpB_{i_p}=B_{j_p}=C_p,且至少存在一个 pp 使 ip≠jpi_p\ne j_p。两组下标允许重叠;子序列不要求连续。

若不存在合法序列,回答 −1-1。否则,取字典序最大的合法序列 CC,输出它的哈希值

$$\left(\sum_{i=1}^{|C|}C_i3^{i-1}\right)\bmod998244353.$$

字典序按第一个不同元素比较;若一个序列是另一个序列的真前缀,则较长者更大。

输入格式

N Q
A_1 A_2 ... A_N
L_1 R_1
...
L_Q R_Q

输出格式

输出 QQ 行,每行一个整数,按输入顺序回答询问。

数据范围

1≤N,Q≤3×1051\le N,Q\le3\times10^5,1≤Ai≤N1\le A_i\le N,1≤Li≤Ri≤N1\le L_i\le R_i\le N。输入均为整数。

样例 1

输入:

5 4
3 2 1 2 3
1 5
1 3
2 4
2 5

输出:

36
-1
2
11

样例 2

输入:

5 1
3 2 1 4 1
1 5

输出:

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

输出:

56
20
56
35
20
56
17
35
20
17