配点 : 100 点
問題文
(1, 2, \ldots, N) 的排列 给出了 P = (P_1, P_2, \ldots, P_N) 和整数 可以获得第 K 。 对于
如果执行如下伪代码表示的算法,公式 (1) 会被执行多少次?
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N - i - K + 2; j++) {
if ((P[j], P[j + 1], ..., P[j + K - 1]) が昇順に並んでいない) {
(P[j], P[j + 1], ..., P[j + K - 1]) を昇順に並び替える ... (1)
}
}
}
制約
- 所有输入均为整数
- 2 \leq K \leq N \leq 2\times 10^5
- P 是 您也可以写 (1,2,\ldots,N) 的排列 给出了
入力
输入是按以下格式从标准输入给出的。
N K P_1 P_2 \ldots P_N
出力
答案 请打印除以 1 行输出。
入力例 1
4 2 1 3 4 2
出力例 1
2
(i, j) = (1, 1) 时,(P_1, P_2) = (1, 3) 并且,公式 (1) 不会被执行。
(i, j) = (1, 2) 时,(P_2, P_3) = (3, 4) 并且,公式 (1) 不会被执行。
(i, j) = (1, 3) 时,(P_3, P_4) = (4, 2) 中,执行了 (1) 式,(P_3, P_4) = (2, 4)。
(i, j) = (2, 1) 时,(P_1, P_2) = (1, 3) 并且,公式 (1) 不会被执行。
(i, j) = (2, 2) 时,(P_2, P_3) = (3, 2) 中,执行了 (1) 式,(P_2, P_3) = (2, 3)。
(i, j) = (3, 1) 时,(P_1, P_2) = (1, 2) 并且,公式 (1) 不会被执行。
全部共执行了 (1) 式 2 次,所以答案是 2 。入力例 2
6 3 5 1 6 4 3 2
出力例 2
6
入力例 3
20 7 10 17 8 1 16 13 14 5 20 19 4 15 18 3 11 2 12 9 7 6
出力例 3
23