题目描述

有一个长度为 $n$ 的整数序列 $S = (s_1, s_2, \dots, s_n)$。

你需要找出满足以下条件的子数组：

• 这个子数组可以 被分成两个连续的非空段（分割点在该子数组内部），并且 每一段内所有元素的和都等于 0。
• 换句话说：如果子数组为 $S[l..r]$（下标从 $l$ 到 $r$，闭区间），那么存在一个分割点 $m$ 满足 $l < m \le r$，使得$$\sum_{i=l}^{m-1} s_i = 0, \quad \sum_{i=m}^{r} s_i = 0.$$

你要找的是 所有满足上述条件的子数组中，长度最短的子数组的长度，以及 在这个最短长度下，有多少个不同的子数组。
如果不存在这样的子数组，输出两个 -1。

注意：
同一个元素可以属于多个不同的子数组。
两个子数组不同，只要它们的起始位置或结束位置不同。

输入格式

输入由两行组成：第一行包含一个数字$N$，代表数组的元素数量

第二行包含$N$个数字 $s_{i}$，代表数组的元素内容

输出格式

输出满足条件数组的最短长度以及该类数组的个数

如果不存在，分别输出 $-1$ 和 $-1$ 。

样例

5
1 -1 1 -1 1

4 2

7
0 100 1 300 2 10 0

-1 -1

7
100 1 -1 3 -2 -1 100

5 1

提示

【样例说明】

第一个样例

注意同一个元素是允许出现在多个不同的子数组中的

本例子中有两种子数组分割方法

方案$1$：$[1$ $-1][1$ $-1]1$

方案$2$：$1[-1$ $1][-1$ $1]$

第三个样例

子数组$\{1$ $-1$ $3$ $-2$ $-1\}$满足条件

其可分为两个满足条件的子子数组$\{1$ $-1\}$和$\{3$ $-2$ $-1\}$

数据范围

前 $30\%$ 的数据 ， $1 \le N \le 500$

前 $60\%$ 的数据 ， $1\le N \le 5000$ 。

前 $100\%$ 的数据， $1\le N \le 10^{6} , -10000\le s_{i} \le 10000$