Набор свёрл

Однажды на рынке Алексей выбирал набор свёрл. В понимании Алексея в «правильном» наборе должны быть свёрла, диаметры которых представляют из себя арифметическую прогрессию с шагом 1. Например, набор 5 2 4 1 3 – правильный, а набор 5 2 4 2 3 – неправильный. Так вот у одного продавца все свёрла лежали в ряд в перемешку.

Помогите Алексею определить сколько у него есть способов выбрать «правильный» набор свёрл.

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

В первой строке входного файла INPUT.TXT находится натуральное число N – количество свёрл у продавца (1 ≤ N ≤ 10⁵). Во второй строке даны N натуральных чисел d_i – диаметры свёрл (1 ≤ d_i ≤ 10⁵).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Пояснение

В примере можно выбрать следующие наборы: [7], [4], [2], [1], [3], [2], [2, 1], [3, 2], [2, 1, 3], [1, 3, 2], [4, 2, 1, 3].

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]