#P17931. Max Twice Subsequences
Max Twice Subsequences
Max Twice Subsequences
给定长度为 的正整数序列 ,回答 个独立的区间询问。每个询问给定 ,令 。
若非空序列 作为 的子序列至少出现两次,则称它为合法序列。严格地说,必须存在两组下标
$$1\le i_1<\cdots<i_k\le |B|,\qquad1\le j_1<\cdots<j_k\le |B|,$$满足对所有 都有 ,且至少存在一个 使 。两组下标允许重叠;子序列不要求连续。
若不存在合法序列,回答 。否则,取字典序最大的合法序列 ,输出它的哈希值
$$\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
输出格式
输出 行,每行一个整数,按输入顺序回答询问。
数据范围
,,。输入均为整数。
样例 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