Яхуб неожиданно открыл секретную лабораторию. Там он нашел n устройств, выстроенных в линию и пронумерованных от 1 до n слева направо. Каждое устройство i (1 ≤ i ≤ n) может создать либо ai единиц материи, либо ai единиц антиматерии.
Яхуб хочет выбрать какой-то непрерывный подотрезок устройств в лаборатории, уточнить тип производства для каждого устройства подотрезка (производить материю или антиматерию) и, наконец, заснять подотрезок. Однако фото будет успешно, только если выделенные устройства произведут одинаковое количество материи и антиматерии (иначе, на фотографии будет лишняя материя или антиматерия).
Вас попросили вычислить количество различных способов, которыми Яхуб может успешно заснять фотографию. Одна фотография отлична от другой, если на ней запечатлен другой подотрезок или по крайней мере одно устройство подотрезка на одной фотографии производит материю, а на другой — антиматерию.
Примечание
Возможные фотографии таковы: [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-], [1+, 2-, 3-, 4+], [1-, 2+, 3+, 4-], [1-, 2+, 3-, 4+] и [1-, 2-, 3+, 4+], где i + означает, что i-ый элемент производит материю, а i - означает, что i-ый элемент производит антиматерию.