# PROBLEM DESCRIPTION :

Sherlock Airlines have come up with a novel way to handle 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 seat number is free, the customer at the head of the line gets the seat. Then, the customer exits the queue.
- If seat is not free, the customer goes back to the end of the line and his preferred seat 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. i.e if customer A has to go back his/her 1st time, he/she carries 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 new penalty is Rs.20 ( 2nd time) and total penalty is Rs.30. The next penalty would be Rs.40 and total penalty to be paid by this customer would be Rs.70.

**Constraints :**

- Total customers say N where 0 < N <= 10000.
- Seats are assigned in increasing order.
- No need to fill prior gaps.

Input :

- First line contains the total number of passengers ‘N’.
- 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 Explanation 1:

There are 2 customers in the group. Customer1 gets seat #1 as the seat is unassigned. When customer2 is at the head of the queue, seat #1 is already assigned and hence, he rejoins the queue at the end with his choice being #2 (previous choice + 1). Seat #2 is available and gets assigned to customer2. Final answer is Rs.10 as Customer #2 was requeued once and hence a penalty of Rs.10.

Sample Input 2:

3

1

1

1

Sample Output 2 :

40

Sample Explanation 2:

There are 3 customers in the group. Customer1 gets seat #1 as its unassigned. When customer2 is at the head of the queue, seat #1 is not available and hence he rejoins the queue at the end / re-queued. His preference is bumped up by 1 to #2. Similarly, Customer3 who also wants seat #1 which is already assigned and hence, he also rejoins the queue at the end with his choice now being #2 (previous choice + 1). Back to Customer2 whose choice of Seat#2 is available and he gets it. Customer3 however get re-queued again as seat#2 is already assigned. His choice is bumped to Seat#3. Finally, Customer3 gets Seat #3 as it is available. So total penalty of Rs.40 ( Rs.10 for 1 requeue for Customer2 and Rs.30 for 2 requeues for Customer3).

# SOLUTION :

*My Approach -* Since Constraints were pretty low , I did a hashing plus Queue Based Implementation for this problem. My code passed 8/12 test cases. I had to change return type of the function from int to long long, otherwise it was only passing 5 test cases.

Here's my code in C++ :

```
long long TotalCustomerPenalties(vector<int> InitialAsk) {
queue<array<long long,3>>q;
int n = InitialAsk.size();
vector<bool>vis(n+1,false);
long long ans =0LL;
for(int&i : InitialAsk){
if(!vis[i])
vis[i]= true;
else {
q.push({i+1,0,1LL});
}
}
while(q.size()>0){
auto curr = q.front();
q.pop();
if(vis[curr[0]]==false){
vis[curr[0]]=true;
ans+=(curr[2]*1LL);
continue;
}
curr[0]++;
curr[1]++;
curr[2]+=(long long)pow(2,curr[1]);
q.push(curr);
}
ans*=10LL;
return ans;
}
```