题目描述

已知数组$A$，数组$A$内元素为带符号整数，希望在该数组内找到满足如下条件的子数组：

子数组可分为两个连续的子子数组，这两个子子数组长度可互不相同，但他们的元素和都为零即满足对于子数组区间$[i,j)$，存在中同元素$k$ $(i<k<j)$，使得$\sum [i, k) = \sum [k, j) = 0$；

希望你找出所有满足上述条件数组中的长度最短的子数组。

输入格式

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

第二行包含$N$个数字 $X_{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 X_{i} \le 10000$