Stack Maximum Difference
Given an array of N integers, for each element A[i], find the absolute difference between the index of the nearest element to its left that is strictly greater than A[i], and the index of the nearest element to its right that is strictly greater than A[i]. If no such element exists on the left, use index 0 for the left boundary. If no such element exists on the right, use index N+1 for the right boundary. Print these differences for all elements in the order they appear in the input array.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print N space-separated integers, where the i-th integer is the calculated difference for A_i.
Constraints
1 <= N <= 200000 1 <= A_i <= 10^9
Example 1
5 4 2 5 3 6
3 2 5 2 6
For 4: NGL is none (boundary 0), NGR is 5 (index 2). Diff = 3-0=3. For 2: NGL is 4 (index 0), NGR is 5 (index 2). Diff = (2+1)-(0+1)=3-1=2. For 5: NGL is none (boundary 0), NGR is 6 (index 4). Diff = (4+1)-(0)=5-0=5. For 3: NGL is 5 (index 2), NGR is 6 (index 4). Diff = (4+1)-(2+1)=5-3=2. For 6: NGL
Example 2
7 1 2 3 4 5 6 7
2 3 4 5 6 7 8
For increasing sequence, only right boundary exists for all elements.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 4 2 5 3 6
7 1 2 3 4 5 6 7