题目描述

给定一个长度为 $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$，$B$ 都是正整数序列 $(A_1,\ A_2,\ \dots,\ A_L)$ 的（不一定连续的）子序列。

在本题的约束条件下，保证这样的 $L$ 至少存在一个。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6 4
1 1 2 1 4 3

输出 #1

9

输入输出样例 #2

输入 #2

14 5
1 1 1 2 3 1 2 4 5 1 1 2 3 1

输出 #2

11

输入输出样例 #3

输入 #3

19 10
1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1

输出 #3

39

说明/提示

约束条件

• $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$
• 输入的所有值均为整数

样例解释 1

需要考虑的 $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)$ 的子序列。