Modern Art 2

题目描述

由于对标准的二维艺术感到厌倦（也对他人抄袭她的作品感到沮丧），伟大的牛类艺术家 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。

7
0
1
4
5
1
3
3

2

提示

在此例中，颜色 1 的区间必须在颜色 4 和 5 的区间之前的某一轮被涂，因此至少需要两轮。 题目来源：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold