427. Sri And Tushar
1
Medium
Given an 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 counts of both Sri and Tushar are the same. If they are, 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 counts of both Sri and Tushar are the same. If they are, 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 counts of both Sri and Tushar are 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