Modern Art 2

栈的应用。记录每个颜色的开始和结束，在开始时进栈，结束时出栈，统计最大的栈深度就可以了。

关键条件是每种颜色只能用一次，所以如果任何时候，如果栈顶的颜色和我们要结束的颜色不一样，那这个顺序就是不可能的。例如这样的顺序:

1 2 1 2

到第二个1的时候，因为2还没有结束，所以是栈顶元素，这时候就应该输出-1了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;  // 1e5
int a[100005];
pi cl[100005];   // start and end of each color
stack<int> st;
int ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cl[i] = {-1,-1};
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        pi c = cl[a[i]];
        cl[a[i]] = {c.first == -1 ? i : c.first, i};
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            if (st.size()) {
                printf("-1"); 
                return 0;
            }
            continue;
        }
        pi c = cl[a[i]];
        if (c.first == i) st.push(a[i]);
        ans = max(ans, (int)st.size());
        if (c.second == i) {
            if (st.top() != a[i]) { // overlapping colors, impossible to paint
                printf("-1");
                return 0;
            }
            st.pop();
        }
    }
    printf("%d", ans);
    return 0;
}