P3668 [USACO17OPEN] Modern Art 2 G

题目描述

伟大的牛艺术家 Picowso 对标准的二维艺术作品感到厌倦（同时也对其他人抄袭她的作品感到沮丧），于是决定转向一种更极简主义的一维风格。

尽管她的画作现在可以用一个长度为 $N$（$1 \leq N \leq 100,000$）的一维颜色数组来描述，但她的绘画风格保持不变：她从一个空白画布开始，并在其上叠加一系列“矩形”颜料，而在这种一维情况下，这些矩形仅仅是区间。她使用每种颜色 $1 \ldots N$ 恰好一次，尽管和以前一样，某些颜色最终可能会被完全覆盖。

令 Picowso 非常沮丧的是，她的竞争对手 Moonet 似乎已经找到了如何复制这些一维画作的方法，使用的策略与之前的问题类似：Moonet 会绘制一组不相交的区间，等待它们干燥，然后再绘制另一组不相交的区间，依此类推。在整个过程中，Moonet 只能为每种颜色绘制最多一个区间。请计算 Moonet 复制给定的一维 Picowso 画作所需的最少轮数。

输入格式

输入的第一行包含 $N$，接下来的 $N$ 行每行包含一个范围在 $0 \ldots N$ 的整数，表示一维画作中每个单元格的颜色（0 表示空白单元格）。

输出格式

请输出复制这幅画作所需的最少轮数，如果这幅画作不可能是 Picowso 的真实作品（即她无法通过叠加一系列区间、每种颜色一个区间的方式绘制它），则输出 -1。

输入输出样例 1

7
0
1
4
5
1
3
3

2

说明/提示

在这个例子中，颜色 1 的区间必须在颜色 4 和 5 的区间之前绘制，因此至少需要两轮。