配列がスタックソート可能かどうかをチェックする

1 から n の数字が任意の順序で並んだ配列 A が与えられたとき、この配列がスタックを使ってソート(以下、スタックソート (stack-sort) と呼ぶ)できるかどうかを判定します。A がスタックソート可能とは、補助スタックを用いて操作を行った結果、最終的に生成される配列 B が昇順に並ぶようにできることをいいます。許可される操作は次の 2 つです:
  1. A の先頭要素を取り出し、スタックにプッシュする。
  1. スタックのトップ要素を取り出して 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 = []
  1. Operation 1: A = [1, 2, 3], S = [4], B = []
  1. Operation 1: A = [2, 3], S = [4, 1], B = []
  1. Operation 2: A = [2, 3], S = [4], B = [1]
  1. Operation 1: A = [3], S = [4, 2], B = [1]
  1. Operation 2: A = [3], S = [4], B = [1, 2]
  1. Operation 1: A = [], S = [4, 3], B = [1, 2]
  1. Operation 2: A = [], S = [4], B = [1, 2, 3]
  1. Operation 2: A = [], S = [], B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
  1. Operation 1: A = [2, 1], S = [3], B = []
  1. Operation 1: A = [1], S = [3, 2], B = []
  1. Operation 1: A = [], S = [3, 2, 1], B = []
  1. Operation 2: A = [], S = [3, 2], B = [1]
  1. Operation 2: A = [], S = [3], B = [1, 2]
  1. Operation 2: A = [], S = [], B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
  1. Operation 1: A = [2, 3], S = [1], B = []
  1. Operation 2: A = [2, 3], S = [], B = [1]
  1. Operation 1: A = [3], S = [2], B = [1]
  1. Operation 2: A = [3], S = [], B = [1, 2]
  1. Operation 1: A = [], S = [3], B = [1, 2]
  1. 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

To check your solution you need to sign in
Sign in to continue