题目描述

我们有一个长度为$N^2$的正整数序列 $A=(A_1, A_2, \dots, A_{N^2})$，以及一个正整数 $S$。对于这个正整数序列，对于任意的正整数 $i\ (1\leq i \leq N^2-N)$，都有 $A_i=A_{i+N}$，只有 $A_1, A_2, \dots, A_N$ 给定作为输入。

寻找最小的整数 $L$，使得每个和为 $S$ 的正整数序列 $B$ 都是正整数序列 $(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