分数: 1000 点
问题陈述
我们有一个长度为正整数的序列 N^2, A=(A_1,\ A_2,\ \dots,\ A_{N^2}),和一个正整数 S。对于这个正整数序列, A_i=A_{i+N} 对于正整数成立 i\ (1\leq i \leq N^2-N),并且仅 A_1,\ A_2,\ \dots,\ A_N 作为输入给出。
求最小整数 L 这样每个序列 B 正整数总计 S 是序列的(不一定是连续的)子序列 (A_1,\ A_2,\ \dots,\ A_L) 正整数。
可以证明至少有一个这样的 L 在这个问题的约束下存在。
约束
- 1 \leq N \leq 1.5 \times 10^6
- 1 \leq S \leq \min(N,2 \times 10^5)
- 1 \leq A_i \leq S
- 对于每个正整数 x\ (1\leq x \leq S), (A_1,\ A_2,\ \dots,\ A_N) 至少包含一次 x.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N S A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
6 4 1 1 2 1 4 3
示例输出 1
9
有八个序列 B 要考虑: B=(1,\ 1,\ 1,\ 1),\ (1,\ 1,\ 2),\ (1,\ 2,\ 1),\ (1,\ 3),\ (2,\ 1,\ 1),\ (2,\ 2),\ (3,\ 1),\ (4).
对于 L=8,例如, B=(2,\ 2) 不是以下的子序列 (A_1,A_2,\ \dots,\ A_8)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1).
对于 L=9,另一方面,每个 B 是以下序列的子序列 (A_1,A_2,\ \dots,\ A_9)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1,\ 2).
示例输入 2
14 5 1 1 1 2 3 1 2 4 5 1 1 2 3 1
示例输出 2
11
示例输入 3
19 10 1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1
示例输出 3
39