旅人铭刻之壁

“一如既往继续旅行、置身于一如既往景色中的她，究竟是谁？ 没错，就是我。”

墙壁上有一副 $n$ 个点的地图，可以抽象为一个长度为 $n$ 的序列 $X$ 。

两个点 $i,j$ 有路径当且仅当满足以下条件之一：

• $|i-j|=1$。
• $X_i=X_j$。

少女想要选择起点 $u$ 和终点 $v$ 来继续她的旅行，并且想要 $(u,v)$ 之间的最短路尽可能长。但她并不满足于此，少女还想知道自己能有多少种不同的旅行方案。而你作为她的一条狗（好伙伴），有义务帮她解决这个问题。

输入格式

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

第二行 $n$ 个数表示序列 $X$ 。

输出格式

一行两个正整数，分别代表这张图的直径和方案数。

图 $G=(V,E)$ 的直径的定义为：$\max\{\text{dist}(i,j)\mid i, j \in V\}$， $\text{dist}(i,j)$ 为 $i, j$ 之间的最短路。

两个长度相等的直径 $\text{diam}(u_1, v_1), \text{diam}(u_2, v_2)$ 不同当且仅当 $\exists\ x \in \text{diam}(u_1, v_1)$ 且 $x \not\in \text{diam}(u_2, v_2)$。

样例 1 输入

3
0 1 2

样例 1 输出

2 1

样例 2 输入

11
1 1 1 1 1 1 1 1 1 1 1

样例 2 输出

1 55

测试点约束

保证 $2 \le n \le 10^5$， $X_i < 8$。

子任务 1（20 pts）

$n \le 500$。

子任务 2（10 pts）

$\forall {i,j \in [1, n] }， X_i = X_j$。

子任务 3（30pts）

$n \le 5000, X_i < 4$。

子任务 4（40 pts）

无特殊限制。