Key cutting

#include <bits/stdc++.h>
using namespace std;
 
const int INF = (int)1e9;
 
struct SegTree {
    vector<int> mins;
 
    SegTree(vector<int> a) : mins(4 * a.size()) {
        build(0, 0, a.size(), a);
    }
 
    void build(int i, int l, int r, const vector<int>& arr) {
        if (l + 1 == r) {
            mins[i] = arr[l];
            return;
        }
 
        int m = (l + r) / 2;
        build(i * 2 + 1, l, m, arr);
        build(i * 2 + 2, m, r, arr);
        mins[i] = min(mins[i * 2 + 1], mins[i * 2 + 2]);
    }
 
    int get(int i, int l, int r, int ql, int qr) {
        if (l >= qr || ql >= r) {
            return INF;
        }
        if (ql <= l && r <= qr) {
            return mins[i];
        }
 
        int m = (l + r) / 2;
        return min(get(i * 2 + 1, l, m, ql, qr),
            get(i * 2 + 2, m, r, ql, qr));
    }
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n = 0;
    cin >> n;
 
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
 
    SegTree st(a);
 
    map<int, int> prev;
    int ans = n;
    for (int i = 0; i < n; ++i) {
        if (prev.count(a[i])) {
            if (st.get(0, 0, n, prev[a[i]], i) == a[i]) {
                ans--;
            }
        } else {
            if (a[i] == 0) {
                ans--;
            }
        }
        prev[a[i]] = i;
    }
 
    cout << ans << endl;
 
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED