给定一个由 $n$ 颗珠子组成的项链，每颗珠子属于 $k$ 种类型之一。珠子按 $1$ 到 $n$ 的整数编号。第 $i$ 号珠子与第 $i+1$ 号和第 $i-1$ 号珠子相邻（如果这些珠子存在）；此外，第 $1$ 号和第 $n$ 号珠子也相邻。我们希望通过两次切割将项链分成两个非空的片段（字符串），使得每种类型的珠子恰好出现在其中一个片段中（即，如果一个片段包含某种类型的珠子，则另一个片段中不包含该类型的珠子）。问这样的划分有多少种，以及所得两个片段长度之差的最小值是多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($2 \le k \le n \le 1\,000\,000$)，用空格分隔，分别表示项链的长度和珠子的种类数。珠子种类编号为 $1$ 到 $k$。输入的第二行包含一个由 $n$ 个整数组成的序列 $r_1, r_2, \dots, r_n$ ($1 \le r_i \le k$)，用空格分隔；数字 $r_i$ 指定了第 $i$ 号珠子的种类。你可以假设每种类型的珠子在项链中至少出现一次。

在总分占比 30% 的测试用例中，满足附加条件 $n \le 1000$。

输出格式

输出一行，包含两个用空格分隔的整数。第一个数字应为合法的项链划分方案数（你可以假设对于输入数据至少存在一种划分方案）。第二个数字应为所得两个片段长度之差的最小值。

样例

输入 1

9 5
2 5 3 2 2 4 1 1 3

输出 1

4 3

说明

共有四种合法的划分方案；较短的片段可以包含以下珠子种类组合之一：(5), (4), (1, 1) 或 (4, 1, 1)。最后一种方案给出了最优的长度差 $6 - 3 = 3$。