Cisco OA-3 2022

Problem Description

Sherlock Airlines has introduced a unique method to manage travelers who don't plan ahead and often try to book the same seat numbers at the travel desk, causing delays since only one person can occupy a seat. The seating arrangement consists of seats in a straight line, and customers line up with their preferred seat numbers. The agents of Sherlock Airlines allocate seats based on the following logic:

• If a seat is available, the customer at the front of the queue is assigned that seat and then leaves the queue.
• If the seat is occupied, the customer returns to the end of the line, and their preferred seat number is increased by 1. Additionally, the customer incurs a penalty for the delay.

Each time a customer has to go to the back of the line due to a seat conflict, the penalty doubles and accumulates. For example:

• If Customer A is sent to the back for the first time, they incur a penalty of Rs. 10.
• If they return to the front and encounter another conflict, the penalty doubles to Rs. 20 (for the second time), bringing their total penalty to Rs. 30.
• The next penalty would be Rs. 40, increasing their total to 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