← 返回题目列表

AtCoder · arc150_f

F. 常数和子序列

中文机器翻译题面 查看原题

分数: 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