potatoqueue

Problem Description

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.

Implementation Details

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.

Limits

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 10⁶

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

Sample Input

join 1
join 7
join 4
query 2
query 3
serve
serve
join 2
query 1
query 2

Sample Output

-1
1
-1
0