There are n people standing in an ATM queue, numbered from 1 to n. Initially, they stand in increasing order of their number.
Person i wants to withdraw amounts[i - 1] units of money. In one turn, a person can withdraw at most maxWithdraw units.
If a person still needs more money after their turn, they go to the end of the queue. Otherwise, they leave the queue.
Return the order in which all people leave the queue.
Method Signature
List<Integer> getExitOrder(List<Integer> amounts, int maxWithdraw)
n = amounts.size().amounts contains the withdrawal amount needed by each person.amounts[i] is the amount needed by person i + 1.maxWithdraw is the maximum amount that can be withdrawn in one turn.- The returned list contains the people numbers in the order they leave the queue.
- If two people leave after the same number of turns, the person with the smaller number leaves first.
Constraints
1 ≤ amounts.size() ≤ 100,0001 ≤ amounts[i] ≤ 1,000,000,0001 ≤ maxWithdraw ≤ 1,000,000,000
Examples
Example 1
Input: getExitOrder(amounts = List.of(5, 1, 9, 4), maxWithdraw = 4)
Output: List.of(2, 4, 1, 3)
Explanation: Person 2 needs 1 turn, person 4 needs 1 turn, person 1 needs 2 turns, and person 3 needs 3 turns. So the exit order is 2, 4, 1, 3.
Example 2
Input: getExitOrder(amounts = List.of(8, 3, 6, 12, 1), maxWithdraw = 5)
Output: List.of(2, 5, 1, 3, 4)
Explanation: Persons 2 and 5 leave after their first turn. Persons 1 and 3 leave after their second turn. Person 4 leaves after the third turn.
Example 3
Input: getExitOrder(amounts = List.of(10, 20, 30, 40), maxWithdraw = 10)
Output: List.of(1, 2, 3, 4)
Explanation: The people need 1, 2, 3, and 4 turns respectively, so they leave in the same order as their numbers.