#ifndef MAIN #define MAIN #include __FILE__ //using mint = modint998244353; void _main(){ cint(n); cstr(s); vector> v(n+1, vector(3, inf)); // 1 streak v[0][0] = v[0][1] = v[0][2] = 0; rep(i, n) { rep(j, 3) { if (s[i] == '1') { v[i+1][0] = v[i+1][1] = *min_element(all(v[i])); v[i+1][2] = min(v[i][1], v[i][2]); } else { v[i+1][0] = v[i][2]; v[i+1][1] = *min_element(all(v[i])) + 1; v[i+1][2] = min(v[i][1], v[i][2]) + 1; } //cerr << v[i+1][j] << ' '; } //cerr << endl; } cout << *min_element(all(v[n])) << endl; } #else #define MAIN #include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using strvec = vector; constexpr ll mod10 = 1000000007; constexpr ll mod9 = 998244353; constexpr ll inf = 10000000000000000; #define int ll #define double ld #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repf(i, s, n) for (int i = s; i < (int)(n); i++) template void __y_input(Args &...arg) { (cin >> ... >> arg); } template void __y_input_vec_1(int p, Args &...args) { (cin >> ... >> args[p]); } template void __y_input_vec_resize(int size, Arg &arg) { arg.resize(size); } template void __y_input_vec(int n, Args &...args) { (__y_input_vec_resize(n, args), ...); rep(i, n) { (__y_input_vec_1(i, args), ...); } } #define cint(...) \ int __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cdbl(...) \ double __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cstr(...) \ string __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cvec(n, ...) \ vector __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvect(t, n, ...) \ vector __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define last cout << endl #define yn(bl) (bl ? "Yes" : "No") #define all(v) v.begin(), v.end() #define acc(v) accumulate(v.begin(), v.end(), 0LL) #define nxp(v) next_permutation(v.begin(), v.end()) ostream &yesno(bool bl) { cout << yn(bl); return cout; } void cyn(bool bl){ cout << (bl ? "Yes" : "No") << endl; } typedef array xy; typedef array xyz; template inline void sort(T &vec) { return sort(vec.begin(), vec.end()); } template inline void rsort(T &vec) { return sort(vec.rbegin(), vec.rend()); } void _main(); template void prefix_sum(vector& p, vector& s){ s.emplace_back(p[0]); for (size_t i = 1; i < p.size(); i++){ s.emplace_back(p[i] + s.back()); } return; } template void compress(T a, T b){ vector m(a, b); sort(all(m)); m.erase(unique(all(m)), m.end()); for (auto itr = a; itr != b; itr++){ *itr = (lower_bound(all(m), *itr) - m.begin()); } } template using rpq = priority_queue, greater>; template void operator+=(vector& v, const T t) { v.emplace_back(t); } signed main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); _main(); return 0; } #endif