Modern Art 2

import java.io.*;
import java.util.*;
 
public class ModernArt2 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("art2.in"));
		PrintWriter out = new PrintWriter(new FileWriter("art2.out"));
		int N = Integer.parseInt(in.readLine());
		int[] start = new int[N + 1];
		int[] end = new int[N + 1];
		Arrays.fill(start, Integer.MAX_VALUE);
		Arrays.fill(end, Integer.MIN_VALUE);
 
		int[] color = new int[N + 1];
		for (int i = 1; i <= N; i++) { color[i] = Integer.parseInt(in.readLine()); }
 
		for (int i = 1; i <= N; i++) {
			// Update the first and last appearance of the color.
			start[color[i]] = Integer.min(start[color[i]], i);
			end[color[i]] = Integer.max(end[color[i]], i);
		}
 
		start[0] = 0;
		end[0] = N + 1;
		int ans = 0;
		// The contents of the stack are the colors of the currently open
		// segments.
		Stack<Integer> stack = new Stack<>();
		for (int idx = 0; idx <= N; idx++) {
			int curColor = color[idx];
 
			// Process the start point of the color segment.
			if (idx == start[curColor]) {
				stack.push(curColor);
				ans = Integer.max(ans, stack.size());
			}
 
			/*
			 * Invalid because there are 2 partially intersecting segments.
			 * For instance if we have a finished painting of 1 1 2 1 2,
			 * it is impossible if we can only paint 1 once.
			 */
			if (stack.get(stack.size() - 1) != curColor) {
				out.println(-1);
				out.close();
				System.exit(0);
			}
 
			// Remove the color from the stack since the segment has closed.
			if (idx == end[curColor]) { stack.pop(); }
		}
 
		// Subtract the color '0' segment.
		out.println(ans - 1);
		out.close();
	}
}

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("art2.in", "r", stdin);
	freopen("art2.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> col(n + 1);
	vector<int> start(n + 1, INT32_MAX);
	vector<int> end(n + 1, INT32_MIN);
 
	// get start, end points
	for (int i = 1; i <= n; i++) {
		cin >> col[i];
		start[col[i]] = min(start[col[i]], i);
		end[col[i]] = max(end[col[i]], i);
	}
 
	int ans = 0;
	start[0] = 0;
	end[0] = n + 1;
	stack<int> active;  // keep track of segments
	for (int i = 0; i <= n; i++) {
		int cur = col[i];
		// insert color at start
		if (i == start[col[i]]) {
			active.emplace(col[i]);
			ans = max(ans, (int)active.size());
		}
 
		/*
		 * Invalid because there are 2 partially intersecting segments.
		 * For instance if we have a finished painting of 1 1 2 1 2,
		 * it is impossible if we can only paint 1 once.
		 */
		if (cur != active.top()) {
			cout << "-1" << endl;
			return 0;
		}
 
		// remove color at end
		if (i == end[col[i]]) active.pop();
	}
 
	// '0' is not a color.
	cout << ans - 1 << endl;
}