题目描述

長さが $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$ つ以上存在することが示せます。

输入格式

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

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

输出格式

答えを出力してください。

题目大意

有一个长度为 $n^2$ 的序列 $\{ a_i \}$ 以及一个整数 $sum$。

对于 $\forall i\in[1,n^2-n]$，这个序列满足 $a_i=a_{i+n}$，在本题中只给出 $n$ 个数 $\{ a_1,\dots,a_n\}$。

现在要求你找到一个最小的整数 $p$，使得所有满足 $\sum_{i} b_i=sum$ 的序列 $\{b_i\}$ 是 $\{a_1,\dots,a_p\}$ 的子序列。

6 4
1 1 2 1 4 3

9

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

11

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

Sample Explanation 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) $ の部分列となります。