分数: 700 点
问题陈述
Snuke 有一个排列 (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).
现在,他将执行以下操作 恰好一次:
- 选择 K 中的连续元素 P 并按升序对它们进行排序。
找出可以产生的排列数: P 操作后。
约束
- 2 \leq N \leq 200000
- 2 \leq K \leq N
- 0 \leq P_i \leq N-1
- P_0,P_1,\cdots,P_{N-1} 都是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
P_0 P_1 \cdots P_{N-1}
输出
打印可以生成的排列数 P 操作后。
示例输入 1
5 3 0 2 1 4 3
示例输出 1
2
两个排列可以生成为 P 操作后: (0,1,2,4,3) 和 (0,2,1,3,4).
示例输入 2
4 4 0 1 2 3
示例输出 2
1
示例输入 3
10 4 2 0 1 3 7 5 4 6 8 9
示例输出 3
6