820. Sri And Tushar
0
Medium
Given an integer array nums of length 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.
* 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