Question

There are N vehicles moving in the right direction on a narrow straight road. Each vehicle i has a top speed S: (the maximum speed with
which a vehicle move) associated with it. Each vehicle tries to move at its top speed but cannot attain the top speed because of the
congestion that has been created by vehicles ahead of them have a lesser speed. For every vehicle i, determine the minimum number of
vehicles it needs to overtake so that it attains its top speed assuming no other vehicle will overtake while computing the answer for the ith
vehicle.
Note: The Nth vehicle is the first in the line. A vehicle i can move at its top speed only when no other vehicles ahead of it are moving a
the top speed less than Si.
Input format
• First line: T denoting the number of test cases
• For each test case:
o First line: N denoting the number of vehicles on the road
o Next line: N space-separated integers representing the top speeds Si of the vehicle i
Output format
Print N space-separated integers and the ith integer representing the number of vehicles it needs to overtake to be able to move at
speed.
Constraints
1 I

Answer 1

Answer:

start from right most element find no of minimum elements encountered yet,that much no of elements will be your answer for that particular element.

this searching time can be logn if you used a container which store elements in sorted way so that seach is easy for you.

overall a nlogn solution