問題文

長さが $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$ のみが入力で与えられます。

総和が $S$ であるような任意の正整数列 $B$ が正整数列 $(A_1,\\ A_2,\\ \\dots,\\ A_L)$ の（連続とは限らない）部分列となるような最小の整数 $L$ を求めてください。

この問題の制約のもとでそのような $L$ が $1$ つ以上存在することが示せます。

制約

• $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$ つ以上含む
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$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