A foundry keeps several furnaces running side by side. Furnace i still holds castings[i] batches of molten metal waiting to be poured. Exactly one furnace is poured during each shift, and to give a furnace's lining time to cool, the same furnace can never be poured on two shifts in a row — though it is free to return to the schedule as soon as at least one other furnace has been poured in between. Assuming the pouring order is chosen as cleverly as possible, find the greatest total number of shifts (equivalently, the greatest total number of batches poured) that can be scheduled before the cooling rule makes it impossible to continue.
n, the number of furnaces.n integers castings[1..n].Print a single integer: the maximum total number of shifts that can be scheduled.
Example 1
Input
3 1 2 3
Expected
6
Explanation
Total batches available is 6, and the busiest furnace (3 batches) is never more than one ahead of the combined 3 batches from the other two furnaces, so every batch can be poured, e.g. in the order furnace3, furnace2, furnace3, furnace1, furnace2, furnace3 — 6 shifts total.
Example 2
Input
3 5 2 1
Expected
7
Explanation
The other two furnaces together only supply 3 batches, which can separate at most 4 of furnace 1's 5 batches (one more than 3). So only 4 of furnace 1's batches plus all 3 of the others' batches — 7 shifts total — can be scheduled; the fifth batch of furnace 1 can never be inserted without repeating it back-to-back.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →