题目描述

长度为 $n$ 的一串项链，每颗珠子是 $k$ 种颜色之一。第 $i$ 颗与第 $i-1,i+1$ 颗珠子相邻，第 $n$ 颗与第 $1$ 颗也相邻。

切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。

求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

输入格式

第一行 $n,k$（$2\leq k\leq n\leq 10^6$）。颜色从 $1$ 到 $k$ 标号。

接下来 $n$ 个数，按顺序表示每颗珠子的颜色。（保证 $k$ 种颜色各出现至少一次）。

输出格式

一行两个整数：方案数量，和长度差的最小值。

9 5
2 5 3 2 2 4 1 1 3

4 3

提示

【样例解释】

四种方法中较短的一条分别是 $(5),(4),(1,1),(4,1,1)$。相差最小值 $6-3=3$。

原题名称：Podział naszyjnika。