A freight depot holds a queue of shipping containers waiting to be logged into the system, each stamped with a positive integer tag. The logging system rejects the whole batch if any two remaining containers share a tag, so the yard operator repeatedly clears containers from the FRONT of the queue: each clearance operation removes exactly three containers from the front (or all remaining containers, if fewer than three are left). The operator stops as soon as every container still in the queue carries a tag different from every other remaining container (an empty queue trivially satisfies this). Given the initial queue, compute the minimum number of clearance operations needed.
Line 1: an integer n, the number of containers. Line 2: n space-separated integers a_1 ... a_n, the tag of each container from the front of the queue to the back.
Print a single integer: the minimum number of clearance operations required.
Example 1
Input
5 1 2 3 4 1
Expected
1
Explanation
Dropping just the single leading container (tag 1) would already leave [2,3,4,1], which has no duplicates — but a clearance operation must remove three containers at a time. One operation removes the first three containers (tags 1,2,3), leaving [4,1], which has no duplicate tags. So one operation suffices, and zero operations leave the original array with two containers tagged 1, which is invalid — so the answer is 1.
Example 2
Input
7 5 5 5 5 5 5 5
Expected
2
Explanation
Every container carries tag 5, so any remaining group of two or more containers still has a duplicate; only a remaining group of at most one container can be duplicate-free. One operation removes 3, leaving 4 containers still tagged 5 (still duplicated). Two operations remove 3+3=6, leaving a single container, which trivially has no duplicate. So two operations is the minimum, giving answer 2.
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 →