Задан целочисленный массив \(a\) размера \(n\).
Назовем массив хорошим, если его можно получить при помощи следующего алгоритма: создать массив, состоящий из одного любого целого числа; а затем произвольное количество раз выполнить следующую операцию: выбрать элемент из уже существующих в массиве (назовем его \(x\)) и в конец массива добавить \(x\), \((x-1)\) или \((x+1)\).
Например, массивы \([1, 2, 1]\), \([5]\) и \([3, 2, 1, 4]\) хорошие, а \([2, 4]\) и \([3, 1, 2]\) — нет.
Ваша задача — посчитать количество хороших непрерывных подмассивов массива \(a\). Два подмассива с одинаковыми элементами, которые различаются своими позициями в массиве \(a\), считаются различными.
Примечание
В первом примере следующие четыре подмассива — хорошие:
- с \(1\)-го по \(1\)-й элемент;
- с \(1\)-го по \(2\)-й элемент;
- с \(2\)-го по \(2\)-й элемент;
- с \(3\)-го по \(3\)-й элемент.
Во втором примере единственный подмассив, не являющийся хорошим, — это подмассив с \(3\)-го по \(4\)-й элемент.