安定ソート (Stable sorting)
いくつかのソートアルゴリズムでは、同じソートキーをもつ要素同士の相対的な順番を維持します。このとき、そのアルゴリズムは安定ソートを行うといいます。
具体例として、配列内の数値と、それぞれの初期インデックスを並べてからソート処理を行ったあと、どのように要素が移動しているかを確認してみましょう。
初期配列 | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
安定ソート | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
不安定ソート | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
安定ソートを行う場合、同じ値をもつ要素同士はもともとの順序を保ちます。しかし、不安定ソートの場合、同じ値をもつ要素であってもその順序が入れ替わる可能性があります。
Challenge
初期の配列として n 個の整数 が与えられ、さらに n 個のインデックス が与えられるとします。このとき、新しい配列は与えられたインデックスの順に要素を並べたもので、最初の要素が 、2 番目の要素が 、…という形になります。
ここで、その新しい配列が、もとの配列を安定ソートした結果と一致するかどうかを判定してください。
入力 (Input)
1 行目に整数 n (1 ≤ n ≤ ) が与えられます。
2 行目に n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。
3 行目に n 個の整数 (0 ≤ < n) が空白区切りで与えられます。
出力 (Output)
もし、与えられたインデックスの順序によって得られる配列が、初期配列を安定ソートしたときの結果と同じであれば
Yes を、そうでなければ No を出力してください。例 (Examples)
入力 | 出力 |
8
10 12 10 7 -3 4 -3 5
4 6 5 7 3 0 2 1 | Yes |
8
10 12 10 7 -3 4 -3 5
6 4 5 7 3 2 0 1 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB