Cisco OA 2022 - Travel Booking Penalties

Sherlock Airlines have come up with a novel way to handle a group of travelers who do not plan ahead and end up trying to book similar seat numbers at the travel desk. In the process, they waste everyone's time since only one person can sit at a seat. Assume all seats are arranged in a straight line & members of the group line up in a queue with their preferred seat number. Agents of Sherlock Airlines allocate seats with this logic:

• If a seat number is free, the customer at the head of the line gets the seat. Then, the customer exits the queue.
• If the seat is not free, the customer goes back to the end of the line, and their preferred seat number is bumped up by 1. Also, the customer incurs a penalty for the delay caused.

Every time a customer goes back to the end of the line due to a conflict, the penalty doubles and accumulates. For example:

• If customer A has to go back his/her 1st time, he/she incurs a penalty of Rs. 10.
• If the next time the customer gets to the front of the line and again has a conflict, the penalty doubles. So the new penalty is Rs. 20 (2nd time), and the total penalty is Rs. 30.
• The next penalty would be Rs. 40, and the total penalty paid by this customer would be Rs. 70.

Constraints:

• The total number of customers is N, where 0 < N <= 10000.
• Seats are assigned in increasing order, no need to fill prior gaps.

Input:

• The first line contains the total number of passengers N.
• The next N lines contain the first choice of the N passengers.

Output:
Return the total number of times customers of the group have been re-queued.

Sample Input 1:
2
1
1

Sample Output 1: 10

Sample Input 2:
3
1
1
1

Sample Output 2: 40