Consider S[i] as Student in position i. Suppose that the input is organized in a vector A, where A[i] means the number of students who are taller and are on the left of S[i].

A[i] means that S[i] is the (A[i]+1)th taller in the subarray S[0 to i], and that's why you process the students from right to left. You can't process from left to right because you don't have enough informations about who's on the right of S[i].

Then you should for every S[i] find what is the (A[i]+1)th larger id available. Here is where the ST is used.

How the ST works:

Each interval [s, e] in the ST has an associated value that means how many available id's exist in this interval.

When querying to find the position of the ith id, the current node will look at it's right child. Suppose that the right child has x available id's, if x >= i it means that the ith larger id is in the right child. If x < i then the ith id is in the left child. If the current node has no children it means that itself contains the ith id.

After finding the position of the ith id it's needed to set this position as no longer available. Just deacrease by 1 the value of all the nodes with intervals that contains this position.

Maybe an example of how it works is better: Testcase: 1 \n 5 \n 0 1 1 3 1

P[] = Values in the leafs of the ST | Res[] = Id's of students

Step 1: P = [1 1 1 1 1], A[i] = 1 | Second larger id is 4. Res = [-1 -1 -1 -1 4]

Step 2: P = [1 1 1 0 1], A[i] = 3 | Fourth larger id is 1. Res = [-1 -1 -1 1 4]

Step 3: P = [0 1 1 0 1], A[i] = 1 | Second larger id is 3. Res = [-1 -1 3 1 4]

Step 4: P = [0 1 0 0 1], A[i] = 1 | Second larger id is 2. Res = [-1 2 3 1 4]

Step 5: P = [0 0 0 0 1], A[i] = 0 | Larger id is 5. Res = [5 2 3 1 4]

Output: 5