/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
A に対して、次の操作をちょうど \mathbf{1} 回行います。
- 1 以上 N-K+1 以下の整数 i をひとつ選ぶ。A _ i,A _ {i+1},\ldots,A _ {i+K-1} を昇順にソートする。より厳密には、A _ i,A _ {i+1},\ldots,A _ {i+K-1} を小さいほうから順に並べたものを B _ 1,B _ 2,\ldots,B _ K とし、1\le j\le K について一斉に A _ {i+j-1} を B _ j で置き換える。
この操作ののち、A が昇順になっている、つまりすべての 1\le i\lt N に対して A _ i\le A _ {i+1} が成り立っているようにできるか判定してください。
制約
- 1\le K\lt N\le2\times10 ^ 5
- 1\le A _ i\le N\ (1\le i\le N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A _ 1 A _ 2 \ldots A _ N
出力
操作を 1 回行うことで A を昇順に並べ替えられるなら Yes を、そうでなければ No を出力せよ。
入力例 1
9 6 1 4 1 4 2 1 3 5 6
出力例 1
Yes
例えば、i として 2 を選ぶと、(A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7)=(4,1,4,2,1,3) が (1,1,2,3,4,4) に置き換えられます。 操作が終わったあとの A は (1,1,1,2,3,4,4,5,6) となり、条件を満たします。
よって、Yes を出力してください。
入力例 2
3 1 3 2 1
出力例 2
No
K=1 なので、どの i に対して操作を行っても A は変化しません。
よって、No を出力してください。
入力例 3
30 25 1 2 2 22 14 10 14 10 18 5 15 8 17 22 10 17 11 25 13 16 9 19 26 7 11 12 23 3 30 30
出力例 3
Yes
Score : 300 points
Problem Statement
You are given a length-N integer sequence A=(A _ 1,A _ 2,\ldots,A _ N).
You will perform the following operation on A exactly once.
- Choose an integer i between 1 and N-K+1, inclusive. Sort A _ i,A _ {i+1},\ldots,A _ {i+K-1} in ascending order. More formally, let B _ 1,B _ 2,\ldots,B _ K be A _ i,A _ {i+1},\ldots,A _ {i+K-1} arranged in increasing order, and simultaneously replace A _ {i+j-1} with B _ j for 1\le j\le K.
Determine whether it is possible that, after this operation, A is in ascending order, that is, A _ i\le A _ {i+1} holds for all 1\le i\lt N.
Constraints
- 1\le K\lt N\le2\times10 ^ 5
- 1\le A _ i\le N\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A _ 1 A _ 2 \ldots A _ N
Output
If A can be sorted in ascending order by performing the operation once, output Yes; otherwise, output No.
Sample Input 1
9 6 1 4 1 4 2 1 3 5 6
Sample Output 1
Yes
For example, if you choose 2 as i, then (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7)=(4,1,4,2,1,3) is replaced with (1,1,2,3,4,4). After the operation, A is (1,1,1,2,3,4,4,5,6), which satisfies the condition.
Thus, output Yes.
Sample Input 2
3 1 3 2 1
Sample Output 2
No
K=1, so A does not change regardless of which i the operation is performed on.
Thus, output No.
Sample Input 3
30 25 1 2 2 22 14 10 14 10 18 5 15 8 17 22 10 17 11 25 13 16 9 19 26 7 11 12 23 3 30 30
Sample Output 3
Yes