Algorithms and Data Structures

Stable sorting

Some sorting algorithms maintain the relative order of the items with equal sort keys. In those cases, we say that the algorithm performs stable sorting.
Imagine we write the numbers in the array and their initial indices so that after sorting we can see where each element was shifted.
Initial array
(10, 0)
(12, 1)
(10, 2)
(7, 3)
(-3, 4)
(-3, 5)
(7, 6)
Stable sorting
(-3, 4)
(-3, 5)
(7, 3)
(7, 6)
(10, 0)
(10, 2)
(12, 1)
Unstable sorting
(-3, 5)
(-3, 4)
(7, 3)
(7, 6)
(10, 2)
(10, 0)
(12, 1)
When performing a stable sort, an algorithm keeps the initial order if the items are equal. Yet, in the case of unstable sorting, that order can be changed.

Challenge

Given an initial array of n integers , and n indices , you should obtain a new array by taking the elements in the order indicated by the given indices. The first element of the new array should be , the second one should be , etc.
You are asked to check if the obtained array is the stable sorted version of the initial array.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ).
The next line contains n space-separated integers ( ≤ ≤ ).
The next line contains n space-separated integers (0 ≤ < n).

Output

The program should print Yes if the order of indices would be the result of performing a stable sort on , and No otherwise.

Examples

Input
Output
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

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