Having tried Jiahai the Potato's delicious Shepherd's Pie, Mr. Panda suggested that he set up a stall to sell his pies and make some money. Hence, he sets up stall with help from Mr. Panda in advertising. Within a few months, the stall gets very famous and his stall starts attracting long queues.
Even though Jiahai the Potato is trying his best to serve the pies as quickly as possible, some people in the queue get impatient for having to wait in the long queue so Mr. Panda is made to deal with the impatient customers. The customers joining the queue are of different heights and each customer can only look over customers in front of them that are strictly shorter than them. The customers want to know how far they are from the front and thus bombard Mr. Panda with the question "How many people are there in front of the last person I can see?". He needs your help to answer these queries AS FAST AS POSSIBLE to keep the customers happy.
Initially, the queue is empty. Your program will have to implement the 4 functions below.
void init(): Initialisation of code
void join(int H): A person of height H joins the back of the queue
void serve(): The front person in the queue is served, there is guaranteed to be someone in the queue
int query(int N): The Nth person from the front makes the query "How many people are there in front of the last person I can see?" and the function should return the answer. If the customer can see the stall and is trolling Mr. Panda, return -1. The query is guaranteed to be valid.
Please use the template provided for coding and for testing purposes you can run
compile_cpp.sh to create a program for testing.
The height of each customer will fit into a 32-bit signed integer.
For all subtasks, the total number of customers and queries will not exceed 106
Subtask 1 (10%): There will be at most 1000 customers and 5000 queries
Subtask 2 (10%): All the customers will be of the same height
Subtask 3 (20%): All calls to query will happen after calls to join and serve
Subtask 4 (20%): No customers will be served :(
Subtask 5 (40%): No restrictions
join 1 join 7 join 4 query 2 query 3 serve serve join 2 query 1 query 2
-1 1 -1 0