Дан массив \(a\) из \(n\) чисел, где все элементы, кроме, возможно, одного, равны \(-1\) или \(1\). Оставшийся элемент \(x\) удовлетворяет условию \(-10^9 \le x \le 10^9\).
Найдите все возможные суммы подмассивов массива \(a\), включая пустой подмассив, сумма которого равна \(0\). Другими словами, найдите все такие числа \(x\), что у массива \(a\) есть хотя бы один подмассив (возможно, пустой) с суммой \(x\). Подмассивом называется непрерывный подотрезок массива.
Выведите эти суммы в порядке возрастания. Каждая сумма должна быть выведена только один раз, даже если достигается на нескольких подмассивах.
Выходные данные
Для каждого набора входных данных выведите две строки:
- в первой строке выведите одно целое число — количество различных сумм на подмассивах;
- во второй строке выведите сами суммы в порядке возрастания.
Каждую сумму следует выводить только один раз, даже если она достигается на нескольких подмассивах.
Примечание
Обозначим за \(a[i,j]\) подмассив массива \(a\) с \(i\)-й позиции по \(j\)-ю позицию.
В первом наборе входных данных примера из условия:
- \(-1\) достигается на подмассиве \(a[2,2]\);
- \(0\) достигается на пустом подмассиве;
- \(1\) достигается на подмассиве \(a[4,4]\);
- \(2\) достигается на подмассиве \(a[4,5]\);
- \(9\) достигается на подмассиве \(a[2,3]\);
- \(10\) достигается на подмассиве \(a[1,3]\);
- \(11\) достигается на подмассиве \(a[3,4]\);
- \(12\) достигается на подмассиве \(a[3,5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 -1 10 1 1
5
-1 -1 -1 -1 -1
2
-1 2
2
7 1
3
1 4 -1
|
8
-1 0 1 2 9 10 11 12
6
-5 -4 -3 -2 -1 0
4
-1 0 1 2
4
0 1 7 8
6
-1 0 1 3 4 5
|