DD HSGHN L9 2022-2023

// O(nlogn)
// Sử dụng kĩ thuật "Phần tử cuối cùng"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
int n;
int a[N], b[N];
int cnt[N * 2];
int last[N], uniq[N];

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

ll Cal(const vector<pair<int, int>> &lm, const vector<pair<int, int>> &rm, const int &l, const int &m, const int &r, int a[N])
{
    ll ans = 0;

    // Imple kĩ thuật "phần tử cuối cùng"
    // uniq[i] = vị trí j lớn nhất mà a[i..j] gồm toàn các phần tử phân biệt
    // Reset mảng
    for (int i = l; i <= r; ++i)
        last[a[i]] = 0;

    for (int i = r, minn = r; i >= l; --i)
    {
        if (last[a[i]] != 0)
            minn = min(minn, last[a[i]] - 1);
        last[a[i]] = i;
        uniq[i] = minn;
    }

    // Maximum and minimum is in a[l..m]
    for (int i = 0, H = 0; i < lm.size(); ++i)
    {
        while (H < rm.size() && rm[H].first > lm[i].first && rm[H].second < lm[i].second)
            ++H;
        if (uniq[m - i] - (m - i) >= lm[i].second - lm[i].first && lm[i].second - lm[i].first >= (m + 1) - (m - i)) // Đoạn này cần có các phần tử phân biệt
            if (H > 0 && H + i >= lm[i].second - lm[i].first)                                                       // Đoạn này cần có rm.first > lm[i].first và rm.second < lm[i].second
                ++ans;
    }

    // Minimum in a[l..m] and maximum in a[m+1..r]
    // Ta duy trì cnt[v] là số lượng j có max[m+1..j]-j = v, do v có thể < 0 nên cộng thêm N vào
    // Reset mảng đếm
    for (int i = 0; i < lm.size(); ++i)
        cnt[lm[i].first - (m - i) + N] = 0;

    for (int i = 0, L = 0, R = 0; i < lm.size(); ++i)
    {
        if (L > uniq[m - i] - (m + 1)) // Đoạn "ứng viên" chắc chắn chứa phần tử trùng
            break;

        while (R < rm.size() && R - 1 <= uniq[m - i] - (m + 1) && rm[R].first > lm[i].first)
        {
            ++cnt[rm[R].second - (R + m + 1) + N];
            ++R;
        }

        while (R - 1 > uniq[m - i] - (m + 1)) // Lùi biên phải của đoạn "ứng viên" để không chứa phần tử trùng
        {
            --R;
            --cnt[rm[R].second - (R + m + 1) + N];
        }

        while (L < R && rm[L].second <= lm[i].second)
        {
            --cnt[rm[L].second - (L + m + 1) + N];
            ++L;
        }
        ans += cnt[lm[i].first - (m - i) + N];
    }

    return ans;
}

ll DAC(int l, int r)
{
    if (l > r)
        return 0;
    if (l == r)
        return 1;

    int m = (l + r) / 2;
    ll ans = DAC(l, m) + DAC(m + 1, r); // Bằng cách này, ta chỉ cần sử dụng một mảng đếm trong hàm Cal()

    vector<pair<int, int>> lm({{a[m], a[m]}}), rm({{a[m + 1], a[m + 1]}});

    // Biểu diễn cặp (minimum, maximum) dưới dạng pair
    // first -> minimum
    // second -> maximum

    for (int i = m - 1; i >= l; --i)
        lm.emplace_back(min(a[i], lm.back().first), max(a[i], lm.back().second));
    for (int i = m + 2; i <= r; ++i)
        rm.emplace_back(min(a[i], rm.back().first), max(a[i], rm.back().second));

    // Đảo ngược dãy <=> swap(lm, rm) và i = n - i + 1
    return ans + Cal(lm, rm, l, m, r, a) + Cal(rm, lm, n - r + 1, n - (m + 1) + 1, n - l + 1, b);
}

void Solve()
{
    // b là reverse của a
    for (int i = 1; i <= n; ++i)
        b[i] = a[n - i + 1];

    cout << DAC(1, n);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}