I am having a difficult time to find an O(N) solution to this problem.

I am using C++. Any help or insight would be appreciated. Thanks

Sorting Description For a given permutation of 1...n , noting it as P. you need to insert the number in P into a set Sone by one, i.e. P1, P2, ...,Pn-1, Pr. After the insertion of each number, you need to find the largest number in Sthat is smaller than the inserted number and the smallest number in Sthat is larger than the inserted number. Initially, two integers 0, n +1 has already been inserted into S so that the results always exist. Input The first line contains a positive integer n. The second line contains n integers, separated by spaces, the i-th integer of which denotes P. Output Print n lines, each line contains two integers separated by a space, the i-th line of which denotes the result required after the insertion of the i-th number. The first integer of a result represents the largest number in that is smaller than the inserted number and the latter one represents the smallest number in that is larger than the inserted number. Sample Input/Output Input 5 1 5 2 4 3 Output 06 16 1 5 2 5 24 Constraint 1<>