#include <cassert>
#include <vector>

using namespace std;

vector<int> solution(int N, vector<int> &A) {

    vector<int> counters;
    counters.resize(N);

    auto base_counter = 0;
    auto max_counter = 0;
    for (auto x: A) {
        assert(x >= 1
               && x <= N + 1);
        if (x >= 1 && x < N + 1) {
            auto &counter = counters[x -1];
            counter = max(counter, base_counter) + 1;
            max_counter = max(max_counter, counter);
        }
        else {
            base_counter = max_counter;
        }
    }

    for (auto& counter: counters) {
        counter = max(counter, base_counter);
    }

    return counters;
}