p02166 Cyclic Shift Sort_28811
Problem

Given a permutation of length $ N $ $ P = \\ {P_1, P_2, \ ldots, P_N \\} $ and the integer $ K $.
Determine if the permutation $ P $ can be monotonically increased by repeating the following operation any number of times $ 0 $ or more.

* Choose the integer $ x \ (0 \ le x \ le N-K) $. Patrol right shift around $ P_ {x + 1}, \ ldots, P_ {x + K} $



However, the cyclic right shift of the subsequence $ U = U_1, \ ldots, U_M $ means that $ U = U_1, \ ldots, U_M $ is changed to $ U = U_M, U_1, \ ldots, U_ {M-1} $. Means to change.

Constraints

The input satisfies the following conditions.

* $ 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) $
* All inputs are integers

Input

The input is given in the following format.


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


Permutation length $ N $ and integer $ K $ are given in the first row, separated by blanks.
The elements of the permutation $ P $ are given in the second row, separated by blanks.

Output

Print "Yes" if you can monotonically increase $ P $, otherwise print "No" on the $ 1 $ line.

Examples

Input

3 3
2 3 1


Output

Yes


Input

3 2
1 2 3


Output

Yes


Input

3 3
3 2 1


Output

No
#include <iostream>
#include <utility>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define llint long long
#define mod 998244353
#define eps 1e-8

using namespace std;

struct BIT{
	int size;
	vector<int> bit;
	BIT(){size = 0;}
	BIT(int s){
		size = s;
		bit.resize(size+1);
		init();
	}
	void init(){
		for(int i = 1; i <= size; i++) bit[i] = 0;
	}
	int query(int i){
		int ret = 0;
		while(i > 0){
			ret += bit[i];
			i -= i&(-i);
		}
		return ret;
	}
	void add(int i, int x){
		while(i <= size){
			bit[i] += x;
			i += i&(-i);
		}
	}
};

llint n, k;
llint p[100005];
BIT bit(100005);

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> p[i];
	
	if(n == k){
		for(int i = 0; i < n; i++) p[i] = p[i+1]-1;
		int x;
		for(int i = 0; i < n; i++){
			if(p[i] == 0){
				x = i;
				break;
			}
		}
		for(int i = 0; i < n; i++){
			if(p[(x+i)%n] != i){
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
		return 0;
	}
	
	int inv = 0;
	for(int i = 1; i <= n; i++){
		inv += (i-1) - bit.query(p[i]);
		bit.add(p[i], 1);
	}
	///cout << inv << endl;
	
	if(k % 2 == 0) cout << "Yes" << endl;
	else{
		if(inv % 2 == 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	
	return 0;
}

3 2
1 2 3 3 3
3 2 1 3 3
2 3 1 3 2
1 2 5 3 1
3 2 1 0 3
2 3 1 0 4
2 3 1 0 3
3 3 1 3 2
2 2 3 3 2
2 2 5 0 3
4 3 1 0 4
3 3 1 0 3
3 0 1 0 2
2 2 3 0 2
4 3 1 0 3
3 1 1 0 2
2 4 3 0 2
6 3 1 0 3
3 2 1 0 2
3 4 3 0 2
6 6 1 0 3
4 2 1 1 2
3 4 3 0 2
6 6 0 0 5
4 2 1 1 2
6 6 0 0 5
4 1 1 0 4
4 1 1 0 2
4 1 1 0 2
4 2 1 1 2
4 2 1 1 2
8 2 1 1 2
8 1 1 1 2
8 1 2 1 0
8 1 2 1 2
1 2 5 1 4
2 3 1 0 2
3 3 1 3 2
2 2 2 3 4
2 2 5 0 3
3 5 1 0 3
3 -1 1 0 2
2 0 3 0 2
4 4 1 0 1
2 2 3 0 2
6 3 2 0 3
0 2 1 0 2
3 4 5 0 2
6 11 1 0 3
5 2 1 1 2
3 4 5 1 2
3 6 0 0 5
4 2 2 0 5
4 0 1 0 2
4 1 2 1 2
8 2 2 1 2
10 2 2 1 4
2 0 1 1 2
3 3 1 3 8
2 2 5 0 1
2 0 3 0 2
4 4 2 0 2
9 3 2 0 3
0 2 0 0 2
3 5 3 0 2
6 7 1 0 3
5 2 0 0 2
3 6 0 0 5
3 0 1 0 2
2 1 2 1 2
8 2 3 0 2
10 2 2 1 2
1 3 1 0 2
2 -1 3 0 2
9 5 2 0 3
0 1 0 0 3
3 5 3 0 2
6 7 0 0 3
7 2 0 0 5
3 -1 1 0 1
2 1 2 1 2
6 2 3 1 3
1 3 1 0 2
16 5 2 0 3
-1 1 0 0 3
5 5 3 0 2
6 7 -1 0 3
7 0 0 0 1
4 1 2 1 2
6 3 3 1 3
1 3 2 0 2
16 5 1 0 1
-1 1 0 0 3
5 5 5 0 2
6 7 -2 0 3
5 0 0 1 2
6 3 0 1 3
1 3 3 0 2
16 9 1 0 1
0 1 0 0 3
5 5 10 0 3
6 7 -2 0 3
5 -1 0
Yes No Yes Yes
 No
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
 Yes
