Sum of Next Greater Element Pairs
MediumPractice library · +20 XPstackarraymonotonic stack
Given an array of N distinct integers, for each element, find the smallest element to its right that is strictly greater than it. If no such element exists, consider it 0. Calculate the sum of these 'next greater elements' for all elements in the array.
Input
The first line contains an integer N. The second line contains N space-separated integers, representing the array elements.
Output
Print a single integer, the sum of the next greater elements for all elements in the array.
Constraints
1 <= N <= 200000 1 <= arr[i] <= 10^9 All elements in the array are distinct.
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 3 2 4 5
Output
16
Next greater elements: 3 (for 1), 4 (for 3), 4 (for 2), 5 (for 4), 0 (for 5). Sum = 3 + 4 + 4 + 5 + 0 = 16.
Example 2
Input
4 5 4 3 2
Output
0
Next greater elements: 0 (for 5), 0 (for 4), 0 (for 3), 0 (for 2). Sum = 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 3 2 4 5
Example 2 input
4 5 4 3 2