問題文

(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) の順列

入力例 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) 式は実行されません。

入力例 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