820. Sri And Tushar

0

Medium

Given an integer array nums of length

* 0 <= i < j < n

* nums[i] > nums[j]

On the other hand, Tushar wants to count the number of local inversions, which is the number of indices i where:

* 0 <= i < n - 1

* nums[i] > nums[i + 1]

You need to determine if the count of both Sri and Tushar is the same. If they are the same, print "YES"; otherwise, print "NO" without quotes.

**n**, which represents a permutation of all the integers in the range [0, n - 1], Sri wants to count the number of different pairs (i, j) where:* 0 <= i < j < n

* nums[i] > nums[j]

On the other hand, Tushar wants to count the number of local inversions, which is the number of indices i where:

* 0 <= i < n - 1

* nums[i] > nums[i + 1]

You need to determine if the count of both Sri and Tushar is the same. If they are the same, print "YES"; otherwise, print "NO" without quotes.

Input Format

The first line contains an integer N, the size of the array.

The second line contains N space-separated integers a0, a1, a2, ..., an-1, describing the array.

The second line contains N space-separated integers a0, a1, a2, ..., an-1, describing the array.

Output Format

Print "YES" if the count of both Sri and Tushar is the same; otherwise, print "NO" without quotes.

Example

Input

3
1 0 2

Output

YES

Constraints

1 <= n <= 10^5

0 <= nums[i] < n

All the integers of nums are unique.

nums is a permutation of all the numbers in the range [0, n - 1].

0 <= nums[i] < n

All the integers of nums are unique.

nums is a permutation of all the numbers in the range [0, n - 1].

Loading...

View Submissions

Console