You are given an array of $n$ bits (zeros and ones). Find the maximum number of parts the array can be partitioned into, such that each part consists of adjacent elements, and contains at least two different bits. Each bit should belong to exactly one part, and the order of the bits cannot be changed.
The first line of input contains a single integer $n$ ($2 \le n \le 10^5$), representing the number of bits.
The second line contains $n$ space-separated bits. It's guaranteed that at least two bits in the array will be different.
Print the maximum number of partitions on a single line.
In the first sample test, the array can be partitioned into 4 valid parts in multiple ways. For example: 0 1 | 1 0 0 | 0 1 | 1 0.
| Input | Output |
|---|---|
9 0 1 1 0 0 0 1 1 0 Copy
|
4 Copy
|
48 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 Copy
|
19 Copy
|
#include <iostream>
using namespace std;
int main() {
int n, last=-1, res=0, x;
cin>>n;
for(int i=0;i<n;++i){
cin>>x;
if(last !=-1 && x!=last){
++res;
last = -1;
}
else last = x;
}
cout<<res<<endl;
return 0;
}