import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Euler1002 {

    static final class SolveResult {
        final boolean bipartite;
        final int answer;
        final long crossings;
        final int components;

        SolveResult(boolean bipartite, int answer, long crossings, int components) {
            this.bipartite = bipartite;
            this.answer = answer;
            this.crossings = crossings;
            this.components = components;
        }
    }

    static final class ParityDsu {
        private final int[] parent;
        private final int[] parity;
        private final int[] size;
        private final int[][] counts;

        ParityDsu(int n) {
            parent = new int[n];
            parity = new int[n];
            size = new int[n];
            counts = new int[n][2];
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
                size[i] = 1;
                counts[i][0] = 1;
                counts[i][1] = 0;
            }
        }

        // returns { root, parityToRoot }
        int[] find(int x) {
            if (parent[x] == x) {
                return new int[] { x, 0 };
            }
            int[] root = find(parent[x]);
            parity[x] ^= root[1];
            parent[x] = root[0];
            return new int[] { parent[x], parity[x] };
        }

        boolean unite(int a, int b) {
            int[] fa = find(a);
            int[] fb = find(b);
            int ra = fa[0], pa = fa[1];
            int rb = fb[0], pb = fb[1];
            if (ra == rb) {
                return (pa ^ pb) == 1;
            }

            int link = pa ^ pb ^ 1;
            if (size[ra] < size[rb]) {
                parent[ra] = rb;
                parity[ra] = link;
                counts[rb][0] += counts[ra][link];
                counts[rb][1] += counts[ra][link ^ 1];
                size[rb] += size[ra];
            } else {
                parent[rb] = ra;
                parity[rb] = link;
                counts[ra][0] += counts[rb][link];
                counts[ra][1] += counts[rb][link ^ 1];
                size[ra] += size[rb];
            }
            return true;
        }

        int bestSum() {
            int total = 0;
            for (int i = 0; i < parent.length; ++i) {
                if (parent[i] == i) {
                    total += Math.max(counts[i][0], counts[i][1]);
                }
            }
            return total;
        }

        int componentCount() {
            int total = 0;
            for (int i = 0; i < parent.length; ++i) {
                if (parent[i] == i) {
                    ++total;
                }
            }
            return total;
        }
    }

    static int[] parseCsvArray(String text) {
        List<Integer> values = new ArrayList<>();
        for (String token : text.split(",")) {
            if (token.trim().isEmpty()) {
                continue;
            }
            long value = Long.parseLong(token.trim());
            if (value < 0 || value > Integer.MAX_VALUE) {
                throw new RuntimeException("Array value is out of range");
            }
            values.add((int) value);
        }
        int[] result = new int[values.size()];
        for (int i = 0; i < result.length; ++i) {
            result[i] = values.get(i);
        }
        return result;
    }

    static int[] readCsvArray(String path) throws IOException {
        return parseCsvArray(new String(Files.readAllBytes(Paths.get(path))));
    }

    // intervals[i] = { left, right }, sorted by left
    static int[][] buildIntervals(int[] a) {
        if (a.length % 2 != 0) {
            throw new RuntimeException("Array length is odd");
        }
        int n = a.length / 2;
        int[] first = new int[n];
        int[] occurrences = new int[n];
        for (int i = 0; i < n; ++i) {
            first[i] = -1;
        }
        List<int[]> intervals = new ArrayList<>();

        for (int pos = 0; pos < a.length; ++pos) {
            int value = a[pos];
            if (value < 0 || value >= n) {
                throw new RuntimeException("Array values must be in [0,n)");
            }
            ++occurrences[value];
            if (occurrences[value] == 1) {
                first[value] = pos;
            } else if (occurrences[value] == 2) {
                intervals.add(new int[] { first[value], pos });
            } else {
                throw new RuntimeException("A value occurs more than twice");
            }
        }

        for (int count : occurrences) {
            if (count != 2) {
                throw new RuntimeException("A value does not occur exactly twice");
            }
        }

        intervals.sort((x, y) -> Integer.compare(x[0], y[0]));
        return intervals.toArray(new int[0][]);
    }

    static boolean crosses(int[] lhs, int[] rhs) {
        if (lhs[0] < rhs[0]) {
            return lhs[0] < rhs[0] && rhs[0] < lhs[1] && lhs[1] < rhs[1];
        }
        return rhs[0] < lhs[0] && lhs[0] < rhs[1] && rhs[1] < lhs[1];
    }

    static SolveResult solveArray(int[] a) {
        int[][] intervals = buildIntervals(a);
        int n = intervals.length;
        ParityDsu dsu = new ParityDsu(n);
        // encode active intervals as (right << 20) | index, ordered by right then index
        TreeSet<Long> activeByRight = new TreeSet<>();
        long crossings = 0;

        for (int i = 0; i < n; ++i) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            Long e = activeByRight.ceiling((long) (left + 1) << 20);
            while (e != null && (e >> 20) < right) {
                int other = (int) (e & 0xFFFFF);
                if (!dsu.unite(i, other)) {
                    return new SolveResult(false, -1, crossings + 1, 0);
                }
                ++crossings;
                e = activeByRight.higher(e);
            }
            activeByRight.add(((long) right << 20) | i);
        }

        return new SolveResult(true, dsu.bestSum(), crossings, dsu.componentCount());
    }

    static SolveResult bruteForceArray(int[] a) {
        int[][] intervals = buildIntervals(a);
        int n = intervals.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (crosses(intervals[i], intervals[j])) {
                    edges.add(new int[] { i, j });
                }
            }
        }

        int best = -1;
        for (int mask = 0; mask < (1 << n); ++mask) {
            boolean ok = true;
            for (int[] edge : edges) {
                if (((mask >> edge[0]) & 1) == ((mask >> edge[1]) & 1)) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                best = Math.max(best, Integer.bitCount(mask));
            }
        }

        return new SolveResult(best >= 0, best, edges.size(), 0);
    }

    static void validateAllWords(int n, int[] word, int[] counts, int pos) {
        if (pos == 2 * n) {
            SolveResult fast = solveArray(word);
            SolveResult brute = bruteForceArray(word);
            assert fast.bipartite == brute.bipartite;
            if (fast.bipartite) {
                assert fast.answer == brute.answer;
                assert fast.crossings == brute.crossings;
            }
            return;
        }

        for (int value = 0; value < n; ++value) {
            if (counts[value] == 2) {
                continue;
            }
            ++counts[value];
            word[pos] = value;
            validateAllWords(n, word, counts, pos + 1);
            --counts[value];
        }
    }

    static void runCheckpoints() {
        assert solveArray(new int[] { 0, 1, 2, 1, 0, 2 }).answer == 2;
        assert solveArray(new int[] { 0, 0, 1, 1, 2, 2 }).answer == 3;
        assert !solveArray(new int[] { 0, 1, 2, 0, 1, 2 }).bipartite;

        for (int n = 1; n <= 4; ++n) {
            int[] word = new int[2 * n];
            int[] counts = new int[n];
            validateAllWords(n, word, counts, 0);
        }
    }

    public static void main(String[] args) throws IOException {
        String filePath = "resources/documents/1002_input.txt";
        boolean doCheckpoints = true;
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                doCheckpoints = false;
            } else if (arg.startsWith("--file=")) {
                filePath = arg.substring("--file=".length());
            } else {
                System.err.println("Unknown argument: " + arg);
                System.exit(1);
            }
        }

        if (doCheckpoints) {
            runCheckpoints();
        }

        int[] values = readCsvArray(filePath);
        SolveResult result = solveArray(values);
        if (!result.bipartite) {
            System.err.println("The interval crossing graph is not bipartite");
            System.exit(2);
        }
        System.out.println(result.answer);
    }
}