G. Утопление
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Юсефа есть массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел.

Он определяет операцию сокращения для любого массива $$$c$$$ длины $$$|c| \ge 3$$$:

  • Выберите индекс $$$i$$$ ($$$1 \lt i \lt |c|$$$) такой, что $$$c_{i-1} + c_{i+1} \gt c_i$$$.
  • Замените тройку $$$\{c_{i-1}, c_i, c_{i+1}\}$$$ одним целым числом $$$x = c_{i-1} - c_i + c_{i+1}$$$.

Новое число $$$x$$$ занимает позицию, ранее занятую тройкой, а длина массива уменьшается на $$$2$$$.

Массив считается хорошим, если его можно свести к одному элементу, выполнив описанную выше операцию ноль или более раз. Заметьте, что массив длины $$$1$$$ всегда является хорошим.

Юсеф хочет, чтобы вы посчитали количество пар $$$(l, r)$$$ ($$$1 \le l \le r \le n$$$) таких, что подмассив $$$a[l, r]$$$ является хорошим.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Описание каждого набора входных данных следует далее.

В первой строке каждого набора входных данных дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива.

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

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

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

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

Пример
Входные данные
4
3
10 20 10
5
1 1 1 1 1
4
5 1 5 1
1
100
Выходные данные
3
9
5
1
Примечание

В первом примере $$$a = [10, 20, 10]$$$. Подмассивы $$$[10]$$$, $$$[20]$$$ и $$$[10]$$$ все хорошие ($$$3$$$ всего). Подмассив $$$[10, 20, 10]$$$ не является хорошим. Чтобы сократить его, нужно выбрать $$$i=2$$$. Условие $$$a_1 + a_3 \gt a_2$$$ становится $$$10 + 10 \gt 20$$$, то есть $$$20 \gt 20$$$ (ложно).

Во втором примере $$$a = [1, 1, 1, 1, 1]$$$:

  • Все $$$5$$$ подмассивов длины $$$1$$$ являются хорошими.
  • Все $$$4$$$ подмассива длины $$$2$$$ не являются хорошими.
  • Все $$$3$$$ подмассива длины $$$3$$$ (то есть $$$[1, 1, 1]$$$) являются хорошими, потому что $$$1 + 1 \gt 1$$$.
  • Все $$$2$$$ подмассива длины $$$4$$$ не являются хорошими.
  • Подмассив длины $$$5$$$ является хорошим: $$$[1, 1, 1, 1, 1] \xrightarrow{i=2} [1, 1, 1] \xrightarrow{i=2} [1]$$$.
  • Итого количество хороших подмассивов $$$= 5 + 3 + 1 = 9$$$.