Input: A array of unique integers, A, its size n.

Output: Two arrays sl and sr each of size n, containing the ’left scores’ and ’right scores’ of the

elements of A respectively. To be precise: sl[i] will contain the left score and sr[i] the right score

of the element A[i] respectively.

The scores are defined as below:

The left score of the element A[i] is defined as: sl[i] = A[j], where j < i, and A[j] > A[i] and j is

the nearest such index to i. Similarly, the right score of the element A[i] is defined as: sr[i] = A[k],

where k > i, and A[k] > A[i] and k is the nearest such index to i.

If no j exists for an i that satisfies the above condition, then sl[i] = 0. Similarly, if no k ex-

ists for an i that satisfies the above condition, then sr[i] = 0.

It should be easy to work out the O(n

2

) algorithm. Design an O(nlgn) algorithm for this problem.

Source: Windows Questions C++