A shipping dock stores ballast crates in a single line, arranged so that their weights never decrease from left to right. A dockhand runs a crane that can grab any two crates on the line whose weights are different from each other and haul both of them away in one motion — the two crates do not need to be adjacent. She repeats this operation as many times as she likes, in any order she chooses, as long as each time she picks two remaining crates with different weights. She stops the moment no two remaining crates have different weights, meaning either at most one crate is left, or every crate still on the line weighs exactly the same.
Given the weights of all the crates, work out the smallest number of crates that can possibly remain on the dock once she is finished.
Line 1: a single integer n — the number of crates. Line 2: n space-separated integers w_1, w_2, ..., w_n — the crate weights, listed in non-decreasing order.
Print a single integer: the minimum possible number of crates remaining.
Example 1
Input
5 1 1 2 2 3
Expected
1
Explanation
The weights are [1, 1, 2, 2, 3]. Haul away one of the 1s together with one of the 2s (they differ), leaving [1, 2, 3]. Haul away the remaining 1 together with the 3 (they differ), leaving just [2]. Only one crate remains and there is no second crate to pair it with, so the process stops with 1 crate left.
Example 2
Input
5 5 5 5 5 7
Expected
3
Explanation
The weights are [5, 5, 5, 5, 7]. The only crate that differs from the rest is the single 7, so it can be hauled away together with exactly one of the 5s, leaving [5, 5, 5]. Every crate left now weighs 5, so no legal move remains and the process stops with 3 crates left.
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 →