← 返回题目列表

AtCoder · agc038_b

B. 对段进行排序

中文机器翻译题面 查看原题

分数: 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