题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Podział naszyjnika

我们有一条由 $n$ 个珠子组成的项链，每颗珠子属于 $k$ 种类型之一。珠子编号为 $1$ 到 $n$，$i$ 号珠子与 $i+1$ 和 $i-1$ 号珠子相邻（若存在），且 $1$ 号和 $n$ 号珠子也相邻。我们希望用两刀将项链切成两个非空部分，确保每种类型的珠子只出现在其中一部分（即若某部分含类型 $j$ 的珠子，另一部分不得含类型 $j$）。请计算有多少种切割方式，以及两部分长度差的最小值。

输入格式

第一行包含两个整数 $n, k$ $(2 \leq k \leq n \leq 1000000)$，分别表示项链长度和珠子类型数。珠子类型编号为 $1$ 到 $k$。

第二行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$ $(1 \leq r_i \leq k)$，$r_i$ 表示 $i$ 号珠子的类型。保证每种类型至少出现一次。

输出格式

输出一行，包含两个整数，第一个表示可行的切割方式数（保证至少有一种方式），第二个表示两部分长度差的最小值。

9 5
2 5 3 2 2 4 1 1 3

4 3

有四种可行分割：较短部分可包含珠子 $(5)$、$(4)$、$(1, 1)$ 或 $(4, 1, 1)$。最后一种情况下，长度差为 $6 - 3 = 3$，是最优解。

附加样例

1. $n=10$，短项链，仅两种可行分割；
2. $n=1000$，每颗珠子类型不同，所有分割均有效；
3. $n=1000000, k=n/2$，项链形式为 $1, \ldots, k, k, \ldots, 1$。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000$。