该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

小灰灰要为校园活动印制一条彩带．彩带从左到右分成 $n$ 格，开始时每一格都是空白．印好后，第 $i$ 格的颜色应当是 $a_i$．颜色的编号为 $1,2,\ldots,m$．

每种颜色的印版最多使用一次：选择一种尚未使用的颜色和一个非空连续区间，将这个区间内的所有格子印成这种颜色．如果格子原来已有颜色，新颜色会覆盖原颜色．

印制分若干轮进行．一轮中可以使用多种颜色，但这一轮选择的所有区间必须两两没有公共格子．这一轮结束后，才能开始下一轮；后面的轮次可以覆盖前面轮次印下的颜色．可以不使用某些颜色．

请问最少需要多少轮，才能使彩带的每一格都变成要求的颜色？如果无法完成，输出 $-1$．

【输入格式】

第一行包含两个整数 $n,m$，分别表示彩带的格数和可用颜色数．

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各格要求的颜色．

【输出格式】

输出一个整数，表示最少需要的轮数；如果无法完成，输出 $-1$．

【样例 1】

输入

6 4
1 2 3 2 1 4

输出

3

解释

可以按照以下方式印制：

• 第一轮，用颜色 $1$ 印制区间 $[1,5]$，用颜色 $4$ 印制区间 $[6,6]$．
• 第二轮，用颜色 $2$ 印制区间 $[2,4]$．
• 第三轮，用颜色 $3$ 印制区间 $[3,3]$．

颜色 $1$ 必须一次印到第 $1$ 格和第 $5$ 格，因此也会印到中间的格子；颜色 $2$ 必须在它之后使用．同理，颜色 $3$ 必须在颜色 $2$ 之后使用．所以至少需要三轮．

【样例 2】

输入

5 2
1 2 1 2 1

输出

-1

解释

颜色 $1$ 的一次印制必须覆盖 $[1,5]$，颜色 $2$ 的一次印制必须覆盖 $[2,4]$．如果先用颜色 $1$，第 $3$ 格最后会是颜色 $2$；如果先用颜色 $2$，第 $2,4$ 格最后会是颜色 $1$．两种颜色也不能在同一轮印制，因此无法完成．

【下发样例】

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：$n=10,m=6$，满足子任务 1．
• Data/sample4.in 与 Data/sample4.ans：$n=2000$，满足子任务 2．
• Data/sample5.in 与 Data/sample5.ans：$n=2\times10^5$，满足子任务 3．
• Data/sample6.in 与 Data/sample6.ans：$n=2\times10^5$，该样例无特殊限制．
• Data/sample7.in 与 Data/sample7.ans：$n=2\times10^5$，该样例无特殊限制．

【数据规模与约定】

对于所有数据，保证 $1\le n,m\le 2\times10^5$，$1\le a_i\le m$，所有输入均为整数．

本题采用捆绑测试．只有通过一个子任务的所有测试点，才能获得该子任务的分数．

【大样例下载链接】

点击下载本题选手目录