首先最终答案序列的每个数肯定是某个区间合并来的，除了这个区间长为 $1$ 的情况其余情况下 $a_i > 3$ 的 $a_i$ 和 $3$ 都是等价的，容易设计一个 DP 状态，$dp_{i, j}$ 表示让前 $i$ 个数递增，结尾为 $j$，其中 $j \in [0, 3]$，转移枚举一个区间合并成某个数，预处理一下是不是可以合并成这个数就可以做到 $\mathcal{O}(n^2)$ 这个量级了。考虑优化，我们发现似乎无从下手，因为没有冗余的状态和转移，那么我们考虑是不是可以通过一些性质减少转移复杂度。由于我们只要对于每个 $x \in [0, 3]$，找到最短的 $[k, i]$ 使得其可以变成 $x$ 即可，这样操作次数最小。我们猜测 $i - k$ 很小，事实上，打表发现对于任意长度为奇数且长度 $\ge 17$ 的区间，可以合并成 $[0, 3]$ 的任何数。记 $K = 17$，对长度为偶数的区间，枚举下拆成一奇一偶或两个奇数区间即可。这样就只要枚举长度 $\le 3K$ 的区间转移了，因为长度 $> 3K$ 的，如果要变成 $x$，可以拆成三段分别变成 $x$，这样操作次数会更少。时间复杂度就降到了 $\mathcal{O}(nK^3)$。然后用一些辅助数组，精细实现即可做到小常数 $\mathcal{O}(nK^2)$，这里参考了哥哥的实现。

namespace Loop1st {
int n, a[N], trans1[1 << 4][1 << 4], trans2[1 << 10][1 << 4], f[N][K], dp[N][4];
int id(int x, int y) { return y * (y + 1) / 2 + x; }
void Main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    // 0 ~ 3 的无序数对共 10 对:
    /*
    (0, 0)
    (0, 1), (1, 1)
    (0, 2), (1, 2), (2, 2)
    (0, 3), (1, 3), (2, 3), (3, 3)
    */
    // trans1[s][t]: 左(奇)区间能合并成 s, 右(奇)区间能合并成 t, 则两区间合并后能凑出的数的集合
    // trans2[s][t]: 左(偶)区间能合并成的 pair 为 s, 其余和 trans1 同理
    for (int s = 0; s < (1 << 4); s++) {
        for (int t = 0; t < (1 << 4); t++) {
            for (int i = 0; i < 4; i++) if (s >> i & 1) {
                for (int j = 0; j < 4; j++) if (t >> j & 1) {
                    auto [x, y] = minmax(i, j);
                    trans1[s][t] |= 1 << id(x, y);
                }
            }
        }
    }
    for (int s = 0; s < (1 << 10); s++) {
        for (int t = 0; t < (1 << 4); t++) {
            for (int i = 0; i < 4; i++)  {
                for (int j = i; j < 4; j++) if (s >> id(i, j) & 1) {
                    for (int k = 0; k < 4; k++) if (t >> k & 1) {
                        int mex = 0; while (mex == i || mex == j || mex == k) mex++;
                        trans2[s][t] |= 1 << mex;
                    }
                }
            }
        }
    }
    // f[l][r - l] 表示 [l, r) 能凑出的结果，区间 DP
    for (int l = n - 1; ~l; l--) {
        for (int r = l + 1; r <= min(l + K - 2, n); r++) {
            if (r == l + 1) {
                f[l][1] = 1 << min(a[l], 3);
            } else if ((r - l) % 2 == 0) {
                for (int i = l + 1; i < r; i += 2) f[l][r - l] |= trans1[f[l][i - l]][f[i][r - i]];
            } else {
                for (int i = l + 2; i < r; i += 2) f[l][r - l] |= trans2[f[l][i - l]][f[i][r - i]];
            }
        }
    }
    // 若有 a[i] > 3 最后作为其本身出现，那么 a[i + 1...n] 都要 > 3，所以是一个递增的后缀
    int suf = n - 1;
    while (suf && a[suf - 1] <= a[suf]) suf--;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < 4; i++) dp[0][i] = 0;
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= n; i++) {
        for (int x = 1; x < 4; x++) dp[i][x] = min(dp[i][x], dp[i][x - 1]);
        if (i == n) ans = min(ans, dp[i][3]);
        else if (i >= suf) ans = min(ans, dp[i][min(a[i], 3)]);
        for (int x = 0; x < 4; x++) {
            for (int j = i + 1; j <= min(n, i + 3 * K); j += 2) {
                if (j == i + 1 && a[i] != x) continue;
                if (j - i >= K || (f[i][j - i] >> x & 1)) dp[j][x] = min(dp[j][x], dp[i][x] + (j - i) / 2);
            }
        }
    }
    if (ans == 0x3f3f3f3f) cout << "-1\n";
    else cout << ans << '\n';
}

}