Поликарп смотрел шоу, где k членов жюри последовательно оценивали участника, начисляя ему некоторое количество баллов (возможно отрицательное, то есть баллы снимали). Изначально у участника было некоторое количество баллов, и каждая оценка последовательно добавлялась к его количеству баллов. Известно, что i-й член жюри поставил оценку ai.
Поликарп не помнит, сколько баллов было у участника до этих k оценок, но помнит, что среди результатов участника, которые озвучивались после того, как каждый из k жюри поставил оценку, точно были n (n ≤ k) значений b1, b2, ..., bn (гарантируется, что все bj различны). Возможно такое, что Поликарп помнит не все озвученные результаты, то есть n < k. Обратите внимание, начальный результат участника не озвучивался.
Перед вами стоит задача определить количество вариантов того, сколько баллов мог иметь участник до оценок жюри.
Выходные данные
Выведите количество вариантов того, сколько баллов мог иметь участник до оценок жюри. Если Поликарп что-то напутал и не существует ни одного подходящего варианта, выведите «0» (без кавычек).
Примечание
В первом примере ответ 3, так как изначально участник мог иметь - 10, 10 или 15 баллов.
Во втором примере только одно подходящее изначальное количество баллов, которое равно 4 002 000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
-5 5 0 20
10
|
3
|
|
2
|
2 2
-2000 -2000
3998000 4000000
|
1
|