Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

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

墙壁上有一副 $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)

无特殊限制。