Problem:

Problem E: Cyclic Shift Sort

Problem

  長さ $N$ の順列 $P = \{ P_1, P_2, \ldots, P_N \} $ と整数 $K$ が与えられる。

  以下の操作を $0$ 回以上任意の回数繰り返すことで、順列 $P$ を単調増加にすることができるかどうか判定せよ。

  

    
整数 $x \ (0 \le x \le N-K)$ を選ぶ。 $ P_{x+1}, \ldots, P_{x+K} $ を巡回右シフトする

  

  ただし、部分列 $U=U_1, \ldots, U_M$ の巡回右シフトとは、 $U=U_1, \ldots, U_M$ を $U=U_M, U_1, \ldots, U_{M-1}$ に変更することを意味する。

Input

入力は以下の形式で与えられる。

$N$ $K$
$P_1$ $\ldots$ $P_N$

  1行目に順列の長さ $N$ 、整数 $K$ が空白区切りで与えられる。

  2行目に順列 $P$ の要素が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  
$2 \leq K \leq N \leq 10^5 $

  
$ 1 \leq P_i \leq N \ (1 \leq i \leq N) $

  
$ P_i \neq P_j \ (i \neq j) $

  
入力はすべて整数

Output

  $P$ を単調増加にすることができるなら"Yes"を、できないのであれば"No"を $1$ 行に出力せよ。

Sample Input 1

3 3
2 3 1

Sample Output 1

Yes

  $ x = 0 $ として操作を $1$ 回行うと、 $P$ を単調増加にすることができる。

Sample Input 2

3 2
1 2 3

Sample Output 2

Yes

  $P$ が初めから単調増加である場合もある。

Sample Input 3

3 3
3 2 1

Sample Output 3

No

  どのように操作を行なったとしても、 $P$ を単調増加にすることはできない。



Sample input:
3 3
2 3 1


Sample output:
Yes

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,k = LI()
    p = LI()
    if n > k:
        if k%2 == 0:
            print("Yes")
        else:
            a = 0
            bit = [0]*(n+1)
            for i in range(n):
                a ^= (i-sum(p[i]))&1
                add(p[i])
            if a:
                print("No")
            else:
                print("Yes")
        return

    else:
        for i in range(n):
            if p[i] == 1:
                break
        for j in range(n):
            if p[(j+i)%n] != j+1:
                print("No")
                return
        print("Yes")
    return


if __name__ == "__main__":
    solve()