#include "sequence.h"

#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int INF = (int) 1e9;
const int maxN = (int) 1e5 * 5 + 10;

struct SegTree {
    int mn[4 * maxN], mx[4 * maxN], add[4 * maxN];

    void push(int v, int l, int r) {
        if (add[v] == 0) return;
        mn[v] += add[v], mx[v] += add[v];
        if (l != r)
            add[v * 2] += add[v], add[v * 2 + 1] += add[v];
        add[v] = 0;
    }

    void update(int v, int l, int r, int tl, int tr, int val) {
        push(v, l, r);
        if (l > tr || r < tl)
            return;
        if (l >= tl && r <= tr) {
            add[v] += val;
            push(v, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(v * 2, l, mid, tl, tr, val);
        update(v * 2 + 1, mid + 1, r, tl, tr, val);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }

    int get_max(int v, int l, int r, int tl, int tr) {
        if(tl > tr) return 0;
        push(v, l, r);
        if (l > tr || r < tl)
            return -INF;
        if (l >= tl && r <= tr)
            return mx[v];
        int mid = (l + r) / 2;
        return max(get_max(v * 2, l, mid, tl, tr), get_max(v * 2 + 1, mid + 1, r, tl, tr));
    }

    int get_min(int v, int l, int r, int tl, int tr) {
        if(tl > tr) return 0;
        push(v, l, r);
        if (l > tr || r < tl)
            return INF;
        if (l >= tl && r <= tr)
            return mn[v];
        int mid = (l + r) / 2;
        return min(get_min(v * 2, l, mid, tl, tr), get_min(v * 2 + 1, mid + 1, r, tl, tr));
    }

    void clear(int v, int l, int r) {
        mn[v] = 0, mx[v] = 0, add[v] = 0;
        if (l == r) return;
        clear(v * 2, l, (l + r) / 2), clear(v * 2 + 1, (l + r) / 2 + 1, r);
    }
};

SegTree T1, T2;

int sequence(int N, std::vector<int> A) {
    set<int> all_x;
    for (int i = 0; i < N; i++) all_x.insert(A[i]);
    vector<int> pos[N + 1];
    int mx = 0;
    for (int i = 0; i < N; i++) pos[A[i]].emplace_back(i);
    for (int i = 0; i < N; i++) mx = max(mx, (int) pos[A[i]].size());
    // int l = 0, r = mx + 1;
    // while (r - l > 1) {
        int mid = 2;
        T1.clear(1, 0, N - 1), T2.clear(1, 0, N - 1);
        for (int i = 0; i < N; i++){
            T1.update(1, 0, N - 1, i, N - 1, 1);
            // T2.update(1, 0, N - 1, i, N - 1, 1);
        }
        bool F = false;
        for (int x: all_x) {
            // for (int i: pos[x])
            //     T2.update(1, 0, N - 1, i, N - 1, -2);
            for (int i: pos[x])
                T1.update(1, 0, N - 1, i, N - 1, -1);
            for (int i = 0; i + mid <= (int) pos[x].size(); i++) {
                int L = pos[x][i], R = pos[x][i + mid - 1];
                int maxSum = T1.get_max(1, 0, N - 1, R, N - 1) - T1.get_min(1, 0, N - 1, 0, L - 1),
                  minSum = T1.get_min(1, 0, N - 1, R, N - 1) - T1.get_max(1, 0, N - 1, 0, L - 1);
                if ((minSum <= -2 && maxSum >= -2 || (minSum <= 2 && maxSum >= 2))) {
                    F = true;
                    break;
                }
            }
            if (F) break;
            for (int i: pos[x])
                T1.update(1, 0, N - 1, i, N - 1, -1);
        }
        // if (F) l = mid;
        // else r = mid;
    // }
    if(F) return 2;
    return 1;
}