Suppose I have an array of 1 to n elements (Basically they are permutation) and I want to store the next bigger element of the i th element. How is it possible in O(N) or O(NlogN) time?

For example, The given array is : [5, 6, 7, 1, 2, 4, 3] of 7 length. Now I want to store all the element's next bigger element (according to indexing order) in O(N) or O(NlogN) time.

The resultant array should look like this : [6, 7, 7, 2, 4, 4, 3].

Here, the next bigger element of 5 is 6, for 6 is 7, for 7 (there is no bigger element than 7 in the next indices) is 7, for 1 is 2, for 2 is 4, for 4 (there is no bigger element than 4 in the next indices) is 4 and for 3 (as last element so it won't have any next bigger element) is 3.

How it can be done? Hope you guys will help me with your ideas :)

Based on this problem, could you please tell me that, what will be the rearrangement of array [1,1,2,3,4,5,6,7,7] ?

I think the best rearrangement is [1,2,3,4,7,7,6,5,1] and here LIS(a) = 5 and LIS(a’) = 4. So, min(LIS(a), LIS(a’)) = 4. So, based on my thought, the answer should be 4. But based on the tutorial, the answer is 5. Why?