AT_arc150_f [ARC150F] Constant Sum Subsequence

[problemUrl]: https://atcoder.jp/contests/arc150/tasks/arc150_f 長さが $ 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/A

N/A

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