OI XX - baj (Alt)

// https://szkopul.edu.pl/problemset/problem/3GXkVUEnWNZRn2C2VpX2uKmq/site/?key=statement

// Autor:  Adam Karczmarz

#include <bits/stdc++.h>

const int MAXN = 1000100, INF = MAXN;
int c[MAXN + 10], d[2][3];

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < (n); ++i) {
        scanf("%d", &c[i]);
    }
    for (int i = 0; i < n; ++i) {
        int *cur = d[i % 2] + 1, *prev = d[1 - i % 2] + 1;
        for (int v = -1; v <= 1; ++v) {
            if (i == 0) {
                cur[v] = v == c[i] ? 0 : INF;
            } else {
                cur[v] = INF;
                for (int u = -1; u <= v; ++u) {
                    if (c[i] == v) {
                        cur[v] = std::min(cur[v], prev[u]);
                    } else if ((v - c[i]) * u > 0) {
                        cur[v] = std::min(cur[v], prev[u] + (v - c[i]) / u);
                    }
                }
            }
        }
    }
    int res = INF;
    for (int v = -1; v <= 1; ++v) {
        res = std::min(res, d[(n - 1) % 2][v + 1]);
    }
    if (res >= INF) {
        puts("BRAK");
    } else {
        printf("%d\n", res);
    }
    return 0;
}