题目描述

给定一个长度为 $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

输入

6 4
1 1 2 1 4 3

输出

9

样例 2

输入

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

输出

11

样例 3

输入

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

输出

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)$ 的子序列。

由 ChatGPT 4.1 翻译