[R73C]贴纸机 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有一台贴纸机，共有 $k$ 种颜色，编号为 $1, 2, \dots, k$。初始时，贴纸机的颜色为 $s$。

现有 $n$ 张贴纸，第 $i$ 张贴纸的目标颜色为 $a_i$。在开始制作前，你可以任意决定这 $n$ 张贴纸的处理顺序。之后，贴纸机将按照该顺序依次处理每张贴纸，每张贴纸恰好处理一次。

对于当前处理的一张目标颜色为 $x$ 的贴纸：

• 制作成功：若贴纸机当前的颜色恰好为 $x$，则该贴纸制作成功。随后，贴纸机会切换到下一种颜色，颜色按照 $1 \to 2 \to \dots \to k \to 1$ 循环变化，即若当前为 $x < k$，切换为 $x+1$；若当前为 $k$，切换为 $1$。
• 制作失败：若贴纸机当前的颜色不为 $x$，则该贴纸制作失败，贴纸报废，贴纸机的当前颜色保持不变。

你的任务是通过合理规划贴纸的处理顺序，求出最多可以成功制作多少张贴纸。

格式

输入格式

第一行包含三个正整数 $n,k,s$，分别表示贴纸数量、颜色数量和贴纸机的初始颜色。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每张贴纸需要的颜色。

输出格式

输出一行一个整数，表示最多可以成功制作的贴纸数量。

样例

样例输入 #1

5 3 2
1 2 1 3 2

样例输出 #1

4

样例解释 #1

若按照目标颜色为 $1,2,3,1,2$ 的顺序处理贴纸，则第一张贴纸制作失败，之后的 $4$ 张贴纸均制作成功。不存在让 $5$ 张贴纸都制作成功的处理顺序，因此答案为 $4$。

样例输入 #2

10 4 3
3 4 1 4 4 2 3 3 4 1

样例输出 #2

7

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$k\le$
$1$	$60$	$2 \times 10^5$
$2$	$40$	$10^9$

对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$2\le k\le 10^9$，$1\le s\le k$，$1\le a_i\le k$。