Statement is not available in English language
D. Шоу с дельфинами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В известном дельфинарии ставят шоу с дельфинами. В этом году организаторы решили добавить в шоу новый номер и удивить зрителей математическими навыками дельфинов. Дельфины умеют складывать числа, но делают это специфическим образом — они склеивают два числа. Например, из чисел $$$12$$$ и $$$3$$$ дельфин может получить число $$$123$$$ путём «сложения».

Тренер готовит дельфина к новому номеру и тренирует его — он показывает ему последовательно $$$n$$$ карточек с числами. Для каждого нового числа дельфин должен определить, можно ли его получить «сложением» каких-то двух карточек, которые тренер показывал ранее. Если число на текущей карточке можно получить «сложением» числа с увиденной ранее карточки два раза подряд, то это тоже учитывалось. Как только дельфин видит число, которое можно получить «сложением» увиденных ранее карточек — он издает специальный звук.

Определите, сколько раз за тренировку дельфин издаст специальный звук.

Входные данные

Первая строка содержит одно целое число $$$n\;(1 \leq n \leq 10^6)$$$ — количество показанных карточек.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2,...,a_n (0 \leq a_i \lt 10^6)$$$ — числа на карточках, записанные без ведущих нулей.

Выходные данные

Выведите одно целое число — количество раз, которое дельфин издаст специальный звук.

Система оценки

Каждый тест оценивается независимо в 4 балла.

Если Ваше решение корректно работает при $$$n \leq 200 $$$, оно получит не менее 28 баллов.

Пример
Входные данные
7
1 23 123 11 21 1 2311
Выходные данные
3
Примечание

Обратите внимание, что если мы используем карточку с $$$0$$$, то в результате получается число с ведущим нулем. Например, в последовательности {0, 1, 1} ответ для последней карточки будет отрицательным, т.к. $$$01$$$ не совпадает с $$$1$$$.

Рассмотрим пример из условия: пусть были показаны карточки {1, 23, 123, 11, 21, 1, 2311} именно в таком порядке. Тогда, увидев карточку $$$123$$$, дельфин вспомнил, что ранее уже видел карточки $$$1$$$ и $$$23$$$, числа на которых при последовательной записи дают $$$123$$$. Аналогично, увидев $$$11$$$, дельфин смог представить это число как дважды повторенное число с карточки $$$1$$$, а увидев $$$2311$$$, дельфин смог представить это число как последовательную запись $$$23$$$ и $$$11$$$. Итого, дельфин издал специальный звук $$$3$$$ раза.