Given an array arr of size n , you need to find the next greater element for each element in the array.

Problem Note

• The next greater element is the first greater element on an element’s right side in the array. e.g., an element arr[j] would be the next greater element of arr[i] such that arr[j] > arr[i] , i < j and j - i is minimum.
• Return an array that consists of the next greater element of array arr .
• Elements for which no greater element exist, consider the next greater element as -1.

Example 1

Input: arr[] = [1, 2, 3, 4, 5]
Output: [2, 3, 4, 5, -1]
Explanation: In the above example, the next greater element are as follows:
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1 (Since no element is greater than 5 on its right side)
So in the resultant array, we'll get [2, 3, 4, 5, -1] as output. 

Example 2

Input: arr[] = [12, 1, 0, 17, 10]
Output: [17, 17, 17, -1, -1]
Explanation: In the above example, the next greater element are as follows:
12 -> 17
1 -> 17
0 -> 17
17 -> -1 (Since no element is greater than 17 on its right side)
10 -> -1 (Since no element is greater than 10 on its right side)
So in the resultant array, we'll get [17, 17, 17, -1, -1] as output.