C. Эри и расширение множеств
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть существует множество, содержащее различные положительные целые числа. Чтобы расширить множество и включить в него как можно больше целых чисел, Эри может выбрать два целых числа $$$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$$$ является великолепным.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — количество великолепных подмассивов.

Пример
Входные данные
6
2
2 2
6
1 3 6 10 15 21
5
6 30 18 36 9
1
1000000000
6
1 1 4 5 1 4
12
70 130 90 90 90 108 612 500 451 171 193 193
Выходные данные
3
18
5
1
18
53
Примечание

В первом наборе входных данных массив $$$a = [2, 2]$$$ имеет $$$3$$$ подмассива: $$$[2]$$$, $$$[2]$$$ и $$$[2, 2]$$$. Для всех них множество содержит только одно целое число $$$2$$$, поэтому оно всегда является последовательным. Все эти подмассивы являются великолепными, поэтому ответ равен $$$3$$$.

Во втором наборе входных данных рассмотрим подмассив $$$[3, 6, 10]$$$. Мы можем выполнить операции следующим образом:

$$$$$$\{3,6,10\} \xrightarrow{x=6,y=10} \{3,6,8,10\} \xrightarrow{x=6,y=8} \{3,6,7,8,10\} \xrightarrow{x=3,y=7} \{3,5,6,7,8,10\}$$$$$$ $$$$$$\xrightarrow{x=3,y=5} \{3,4,5,6,7,8,10\} \xrightarrow{x=8,y=10} \{3,4,5,6,7,8,9,10\}$$$$$$

$$$\{3,4,5,6,7,8,9,10\}$$$ является последовательным множеством, поэтому подмассив $$$[3, 6, 10]$$$ является великолепным.