SOLVE
LATER
You are given an array A of N integers. Now, two functions \(F(X)\) and \(G(X)\) are defined:
\( F(X) \) : This is the smallest number Z such that \( X < Z \le N \) and \(A[X] < A[Z] \)
\( G(X) \) : This is the smallest number Z such that \( X < Z \le N \) and \(A[X] > A[Z] \)
Now, you need to find for each index i of this array \(G(F(i))\), where \( 1 \le i \le N \) . If such a number does not exist, for a particular index i, output 1 as its answer. If such a number does exist, output \(A[G(F(i))]\)
Input :
The first line contains a single integer N denoting the size of array A. Each of the next N lines contains a single integer, where the integer on the \(i^{th}\) line denotes \(A[i]\).
Output :
Print N space separated integers on a single line, where the \(i^{th}\) integer denotes \(A[G(F(i))]\) or 1, if \(G(F(i))\) does not exist.
Constraints:
\(1 \le N \le 30000 \)
\( 0 \le A[i] \le 10^{18} \)
Next Greater Next Smaller
3 --> 7 7 -->1
7 --> 8 8 -->4
1 --> 7 7 --> 4
7 --> 8 8 --> 4
8 --> -1 -1 --> -1
4 --> 5 5 --> 2
5 --> -1 -1 --> -1
2 --> -1 -1 --> -1
Challenge Name
Sapient Global Markets Java Hiring Challenge
Sapient Global Markets Java Hiring Challenge