A community orchestra's rehearsal coordinator has posted a lineup of n rehearsal slots, numbered in the order musicians will play. Slot i has already been booked by a musician who plays instrument type a[i] (instrument types are identified by positive integers, and it's common for several musicians to share the same instrument type).
To keep the evening interesting, the coordinator wants to trim the lineup by removing the fewest possible slots, without changing the relative order of the slots that remain, so that the trimmed lineup can be split into consecutive duets: the 1st and 2nd remaining slots form the first duet, the 3rd and 4th form the second duet, and so on. A duet is only acceptable if its two musicians play different instrument types — but the second musician of one duet and the first musician of the next duet are free to share an instrument type, since they never perform together. The trimmed lineup must also contain an even number of slots overall, so no slot is left without a partner.
Help the coordinator find the minimum number of slots that must be removed.
The first line contains a single integer n — the number of rehearsal slots. The second line contains n space-separated integers a_1, a_2, ..., a_n — the instrument type booked into each slot, in order.
Print a single integer: the minimum number of slots that must be removed so the remaining lineup (in its original relative order) has even length and every consecutive duet pairs two different instrument types.
Example 1
Input
6 1 1 2 2 3 4
Expected
2
Explanation
Scanning left to right while tracking duets: keep slot1 (type1); slot2 (type1) would tie the pending partner of the open first duet, so it is dropped; keep slot3 (type2) to complete duet1 (1 != 2, ok); slot4 (type2) opens duet2; slot5 (type3) completes it (2 != 3, ok); slot6 (type4) opens duet3. The kept run [1,2,2,3,4] has odd length 5, so its last slot is also dropped, leaving [1,2,2,3] — two valid duets, (1,2) and (2,3). Removed slots: the duplicate type-1 slot and the trailing type-4 slot, for a total of 2.
Example 2
Input
8 1 1 1 1 2 2 3 3
Expected
4
Explanation
Slot1 (type1) opens duet1. Slots 2, 3, and 4 (all type1) each tie that duet's pending partner, so all three are dropped. Slot5 (type2) finally completes duet1 (1 != 2). Slot6 (type2) opens duet2; slot7 (type3) completes it (2 != 3, ok); slot8 (type3) opens duet3. The kept run [1,2,2,3,3] has odd length 5, so the trailing slot8 is dropped too, leaving [1,2,2,3]. Total removed: 3 duplicate type-1 slots plus 1 trailing type-3 slot = 4.
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 →