Задача . C. Эри и расширение множеств

Пусть существует множество, содержащее различные положительные целые числа. Чтобы расширить множество и включить в него как можно больше целых чисел, Эри может выбрать два целых числа \(x\neq y\) из множества так, чтобы их среднее \(\frac{x+y}2\) также было целым числом и не содержалось в множестве, и добавить его в множество. Целые числа \(x\) и \(y\) при этом остаются в множестве.

Назовем множество целых чисел последовательным, если, после сортировки элементов, разница между любой парой соседних элементов равна \(1\). Например, множества \(\{2\}\), \(\{2, 5, 4, 3\}\), \(\{5, 6, 8, 7\}\) являются последовательными, в то время как \(\{2, 4, 5, 6\}\), \(\{9, 7\}\) не являются.

Эри любит последовательные множества. Пусть имеется массив \(b\), тогда Эри помещает все элементы из \(b\) в множество. Если после конечного числа описанных выше операций множество может стать последовательным, массив \(b\) называется великолепным.

Обратите внимание, что если одно и то же целое число встречается в массиве несколько раз, мы помещаем его в множество один раз, так как множество всегда содержит различные положительные целые числа.

У Эри есть массив \(a\) из \(n\) положительных целых чисел. Пожалуйста, помогите ему подсчитать количество пар целых чисел \((l,r)\) таких, что \(1 \leq l \leq r \leq n\) и подмассив \(a_l, a_{l+1}, \ldots, a_r\) является великолепным.