配列がスタックソート可能かどうかをチェックする
1 から n の数字が任意の順序で並んだ配列
A が与えられたとき、この配列がスタックを使ってソート（以下、スタックソート (stack-sort) と呼ぶ）できるかどうかを判定します。A がスタックソート可能とは、補助スタックを用いて操作を行った結果、最終的に生成される配列 B が昇順に並ぶようにできることをいいます。許可される操作は次の 2 つです:Aの先頭要素を取り出し、スタックにプッシュする。
- スタックのトップ要素を取り出して
Bの末尾に追加する。
このとき、最終的に
B が昇順になれば、A はスタックソート可能です。入力
最初の行には整数
n (1 ≤ n ≤ ) が与えられます。続く行には
n 個の整数 (1 ≤ ≤ n) が空白区切りで与えられます。出力
もし
A がスタックソート可能であれば Yes、そうでなければ No を出力してください。Examples
入力 | 出力 |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Explanation
A = [4, 1, 2, 3], S = [], B = []
- Operation 1:
A = [1, 2, 3],S = [4],B = []
- Operation 1:
A = [2, 3],S = [4, 1],B = []
- Operation 2:
A = [2, 3],S = [4],B = [1]
- Operation 1:
A = [3],S = [4, 2],B = [1]
- Operation 2:
A = [3],S = [4],B = [1, 2]
- Operation 1:
A = [],S = [4, 3],B = [1, 2]
- Operation 2:
A = [],S = [4],B = [1, 2, 3]
- Operation 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
- Operation 1:
A = [2, 1],S = [3],B = []
- Operation 1:
A = [1],S = [3, 2],B = []
- Operation 1:
A = [],S = [3, 2, 1],B = []
- Operation 2:
A = [],S = [3, 2],B = [1]
- Operation 2:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
- Operation 1:
A = [2, 3],S = [1],B = []
- Operation 2:
A = [2, 3],S = [],B = [1]
- Operation 1:
A = [3],S = [2],B = [1]
- Operation 2:
A = [3],S = [],B = [1, 2]
- Operation 1:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
It’s impossible to stack-sort the array [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB