G - Range Shuffle Query 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
Q 個のクエリが与えられるので処理してください。
クエリでは整数 L, R, X が与えられるので次の問題を解いてください。

A の L 番目から R 番目までの要素を取り出してできる数列 B=(A_L, A_{L+1}, \dots, A_R) があります。
あなたは以下の一連の操作をちょうど 1 回行います。

  • まず、B から値が X 以上の要素を全て取り除く。
  • 次に、B の要素を自由に並べ替える。

操作後の B としてあり得るものは何通りありますか？答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2.5 \times 10^5
  • 1 \leq Q \leq 2.5 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq L \leq R \leq N
  • 1 \leq X \leq N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q 
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

L R X

出力

Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。

入力例 1

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

出力例 1

3
1
6

1 番目のクエリについて、操作後の B としてあり得るものは (1,1,2), (1,2,1), (2,1,1)の 3 通りです。
2 番目のクエリについて、操作後の B としてあり得るものは空の列 () の 1 通りです。

入力例 2

8 6
6 2 4 1 5 1 8 6
5 6 3
1 5 7
1 4 6
4 7 8
4 8 2
5 8 6

出力例 2

1
120
6
3
1
2

Score : 625 points

Problem Statement

You are given a length-N sequence A = (A_1, A_2, \dots, A_N).
Process Q queries.
Each query gives you integers L, R, X and asks you to solve the following.

Let B = (A_L, A_{L+1}, \dots, A_R) be the sequence formed by the L-th through R-th elements of A.
Perform the following procedure exactly once:

  • First, remove from B every element whose value is at least X.
  • Then, rearrange the remaining elements of B arbitrarily.

How many distinct sequences B can result? Find the count modulo 998244353.

Constraints

  • 1 \le N \le 2.5 \times 10^5
  • 1 \le Q \le 2.5 \times 10^5
  • 1 \le A_i \le N
  • 1 \le L \le R \le N
  • 1 \le X \le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i‑th query:

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

L R X

Output

Output Q lines. The i-th line should contain the answer to the i‑th query.

Sample Input 1

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

Sample Output 1

3
1
6

For the first query, there are three possible resulting sequences B: (1,1,2), (1,2,1), and (2,1,1).
For the second query, there is one possible resulting sequence B: the empty sequence ().

Sample Input 2

8 6
6 2 4 1 5 1 8 6
5 6 3
1 5 7
1 4 6
4 7 8
4 8 2
5 8 6

Sample Output 2

1
120
6
3
1
2