题目描述

只有形式化描述

给出 $n$ 个正整数 $a_i$，以如下规则生成无向图 $G=(V,E)$：

• $V=\{1,2,\cdots,n\}$
• $E=\{(u,v)|a_i=a_j\ or\ |i-j|=1\}$

所有无向边的边权均为 1。

请你求出图 $G$ 的直径，以及有多少对点的最短距离等于直径。

直径的定义为最短距离最大的两个点的最短距离值。

输入格式

第一行包含一个正整数 $n$。

第二行包含一个长为 $n$ 的字符串，表示 $a_1,a_2,\cdots a_n$。

输出格式

输出一行两个正整数，表示直径和取到直径的点对个数。

样例 #1

样例输入 #1

8
10010022

样例输出 #1

4 2

提示

样例输入/输出 2

详见下发文件下的 ex_graph2.in/out。

这个数据满足第 $3\sim 4$ 个测试点的限制。

ex_graph1.in
ex_graph1.out
ex_graph2.in
ex_graph2.out

对所有数据，保证 $1\le n\le 10^5,0\le a_i\le 7$。