/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1500 点
問題文
整数 N,K と (1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます．
あなたは以下の操作を好きな回数 (0 回でもよい) 行うことができます．
- 整数 i (1 \leq i \leq N-K+1) を選ぶ． P_i,P_{i+1},\cdots,P_{i+K-1} の中で 1 番目に大きい要素と 2 番目に大きい要素の値を入れ替える．
操作後の P としてあり得る順列の個数を 998244353 で割ったあまりを求めてください．
制約
- 2 \leq K \leq N \leq 250000
- (P_1,P_2,\cdots,P_N) は (1,2,\cdots,N) の順列である．
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N K P_1 P_2 \cdots P_N
出力
答えを出力せよ．
入力例 1
3 3 2 3 1
出力例 1
2
この例では可能な操作は i=1 のみです．
1 回操作すると，P_1,P_2,P_3 の中で 1 番目に大きい要素 (=P_2=3)と 2 番目に大きい要素 (=P_1=2) の値が入れ替わり，P=(3,2,1) になります． さらにもう一度操作すると，P=(2,3,1) になります．
よって，操作後の順列としてあり得るのは P=(2,3,1),(3,2,1) の 2 つです．
入力例 2
3 2 1 3 2
出力例 2
6
入力例 3
10 5 1 2 3 4 5 6 7 8 9 10
出力例 3
144
入力例 4
20 5 8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9
出力例 4
1451520
Score : 1500 points
Problem Statement
You are given integers N and K, and a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).
You can perform the following operation any number of times, possibly zero.
- Choose an integer i (1 \leq i \leq N-K+1). Swap the values of the two greatest elements among P_i,P_{i+1},\cdots,P_{i+K-1}.
Find the number, modulo 998244353, of permutations that P can be after your operations.
Constraints
- 2 \leq K \leq N \leq 250000
- (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \cdots P_N
Output
Print the answer.
Sample Input 1
3 3 2 3 1
Sample Output 1
2
In this case, the operation can only be performed with i=1.
After one operation, the two greatest elements among P_1,P_2,P_3, which are P_2=3 and P_1=2, have their values swapped, and you have P=(3,2,1). After one more operation, you have P=(2,3,1).
Thus, there are two permutations, P=(2,3,1),(3,2,1), that P can be after your operations.
Sample Input 2
3 2 1 3 2
Sample Output 2
6
Sample Input 3
10 5 1 2 3 4 5 6 7 8 9 10
Sample Output 3
144
Sample Input 4
20 5 8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9
Sample Output 4
1451520