Caesar Legions

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
ifstream fin("caesar.in");
ofstream fout("caesar.out");
struct my_rmq {
    long long mini;
    long long maxi;
};
vector<long long> lg;
vector<vector<my_rmq>> rmq;
long long query(long long st, long long dr, bool maxim) {
    long long pow_2 = lg[dr - st + 1];
    if (maxim) {
        return max(rmq[st][pow_2].maxi, rmq[dr - (1 << (pow_2)) + 1][pow_2].maxi);
    }
    else {
        return min(rmq[st][pow_2].mini, rmq[dr - (1 << (pow_2)) + 1][pow_2].mini);
    }
}
int main() {
    long long n;
    fin >> n;
    vector<long long> a(n + 1);
    for (long long i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    lg = vector<long long>(n + 1);
    for (long long i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }
    rmq = vector<vector<my_rmq>>(n + 1, vector<my_rmq>(lg[n] + 1));
    map<long long, long long> left;
    map<long long, long long> right;
    for (long long i = 1; i <= n; ++i) {
        right[a[i]] = i;
    }
    for (long long i = n; i >= 1; --i) {
        left[a[i]] = i;
    }
    vector<long long> st(n + 1);
    vector<long long> dr(n + 1);
    for (long long i = 1; i <= n; ++i) {
        st[i] = left[a[i]];
    }
    for (long long i = 1; i <= n; ++i) {
        dr[i] = right[a[i]];
    }
    for (long long i = 1; i <= n; ++i) {
        rmq[i][0].mini = st[i];
        rmq[i][0].maxi = dr[i];
    }
    for (long long j = 1; j <= lg[n]; ++j) {
        for (long long i = 1; i + (1 << j) - 1 <= n; ++i) {
            rmq[i][j].maxi = max(rmq[i][j - 1].maxi, rmq[i + (1 << (j - 1))][j - 1].maxi);
            rmq[i][j].mini = min(rmq[i][j - 1].mini, rmq[i + (1 << (j - 1))][j - 1].mini);
        }
    }
    vector<long long> dp(n + 1);
    dp[n] = 1;
    map<long long, long long> closest;
    closest[dr[n]] = n;
    for (long long i = n - 1; i >= 1; --i) {
        long long maxi = query(i, dr[i], true);
        if (maxi == dr[i]) {
            dp[i] = dr[i] - i + 1;
        }
        else {
            dp[i] = closest[maxi] - i + dp[closest[maxi]];
        }
        closest[dr[i]] = i;
    }
    vector<long long> cnt(n + 2);
    for (long long i = n; i >= 1; --i) {
        if (query(i, i + dp[i] - 1, false) >= i) {
            cnt[i] = 1 + cnt[i + dp[i]];
        }
    }
    long long ans = 0;
    for (long long i = 1; i <= n; ++i) {
        ans += cnt[i];
    }
    fout << ans;
}