Question
Calculate Total Rank Gap
Your company is organizing a competition for new hires. There are N participants, each with a unique rank Ri (1 ≤ Ri ≤ N), forming an array R, which is a permutation of numbers from 1 to N. The company has tasked you with finding the total gap in the ranking results.
The total gap is the sum of the gaps for every possible subarray of R. To calculate the gap for a subarray defined by indices [L, R], first sort the subarray in ascending order. The gap is the number of positions i in this subarray where the difference between consecutive ranks Ri - Ri-1 > 1. Your task is to compute and print the total gap for the entire array R.
Input
First line of the input contains a single integer N, the number of participants.
The second line of the input contains N space-separated integers Ai (1 ≤ i ≤ N)
Constraints:
1 ≤ N ≤ 103
1 ≤ Ai ≤ N, All Ai are unique.
The second line of the input contains N space-separated integers Ai (1 ≤ i ≤ N)
Constraints:
1 ≤ N ≤ 103
1 ≤ Ai ≤ N, All Ai are unique.
Output
Print the total gap for the entire array R.
Example
Sample Input
4
2 3 1 4
Sample Output
3
Explanation
Subarrays of size 1:
[2] -> [2], disparity = 0
[3] -> [3], disparity = 0
[1] -> [1], disparity = 0
[4] -> [4], disparity = 0
Subarrays of size 2:
[2, 3] -> [2, 3], disparity = 0
[3, 1] -> [1, 3], disparity = 1
[1, 4] -> [1, 4], disparity = 1
Subarrays of size 3:
[2, 3, 1] -> [1, 2, 3], disparity = 0
[3, 1, 4] -> [1, 3, 4], disparity = 1
Subarrays of size 4:
[2, 3, 1, 4] -> [1, 2, 3, 4], disparity = 0
Total disparity = 3
4
2 3 1 4
Sample Output
3
Explanation
Subarrays of size 1:
[2] -> [2], disparity = 0
[3] -> [3], disparity = 0
[1] -> [1], disparity = 0
[4] -> [4], disparity = 0
Subarrays of size 2:
[2, 3] -> [2, 3], disparity = 0
[3, 1] -> [1, 3], disparity = 1
[1, 4] -> [1, 4], disparity = 1
Subarrays of size 3:
[2, 3, 1] -> [1, 2, 3], disparity = 0
[3, 1, 4] -> [1, 3, 4], disparity = 1
Subarrays of size 4:
[2, 3, 1, 4] -> [1, 2, 3, 4], disparity = 0
Total disparity = 3