A relay station buffers incoming signal codes in a queue awaiting processing, oldest signal first. Before the buffered signals can be relayed onward, every remaining code in the queue must be unique — an empty queue trivially satisfies this. To clear out stale duplicates, an operator repeatedly runs a purge: a purge always discards exactly the three oldest signals still at the front of the queue, except when fewer than three signals remain, in which case it discards all of them at once. Given the queue's signal codes in arrival order, determine the minimum number of purges needed until every remaining signal code is distinct.
Line 1: an integer n — the number of signal codes currently buffered in the queue.
Line 2: n space-separated integers code_1 ... code_n, listed oldest first, the codes currently in the queue.
A single integer: the minimum number of purges required so that all remaining signal codes (or none at all, if the queue empties) are pairwise distinct.
Example 1
Input
9 1 2 3 2 5 3 3 5 7
Expected
2
Explanation
After one purge the three oldest codes (1, 2, 3) are dropped, leaving [2, 5, 3, 3, 5, 7], which still has duplicated 3's and 5's. A second purge drops the next three oldest (2, 5, 3), leaving [3, 5, 7], which is fully distinct. No single purge could have worked, so the minimum is 2.
Example 2
Input
4 8 7 6 5
Expected
0
Explanation
The four codes 8, 7, 6, 5 are already pairwise distinct, so zero purges are needed.
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 →