Давайте рассмотрим следующий процесс: изначально у вас есть пустой стек и массив \(s\) длины \(l\). Вы пытаетесь добавлять элементы массива в стек в порядке \(s_1, s_2, s_3, \dots s_{l}\). Причем если стек пустой или элемент на вершине стека не равен текущему, то вы просто добавляете текущий элемент на вершину стека. Иначе вы не добавляете элемент и более того, удаляете верхний элемент стека.
Если после данного процесса стек окажется пустым, то массив \(s\) считается стек-уничтожимым.
Примеры стек-уничтожимых массивов:
- \([1, 1]\);
- \([2, 1, 1, 2]\);
- \([1, 1, 2, 2]\);
- \([1, 3, 3, 1, 2, 2]\);
- \([3, 1, 3, 3, 1, 3]\);
- \([3, 3, 3, 3, 3, 3]\);
- \([5, 1, 2, 2, 1, 4, 4, 5]\);
Давайте рассмотрим изменения стека более подробно при \(s = [5, 1, 2, 2, 1, 4, 4, 5]\) (элемент на вершине текста выделен жирным шрифтом).
- после добавления \(s_1 = 5\) стек будет равен \([\textbf{5}]\);
- после добавления \(s_2 = 1\) стек будет равен \([5, \textbf{1}]\);
- после добавления \(s_3 = 2\) стек будет равен \([5, 1, \textbf{2}]\);
- после добавления \(s_4 = 2\) стек будет равен \([5, \textbf{1}]\);
- после добавления \(s_5 = 1\) стек будет равен \([\textbf{5}]\);
- после добавления \(s_6 = 4\) стек будет равен \([5, \textbf{4}]\);
- после добавления \(s_7 = 4\) стек будет равен \([\textbf{5}]\);
- после добавления \(s_8 = 5\) стек станет пустым.
Вам задан массив \(a_1, a_2, \ldots, a_n\). Вам нужно посчитать количество подотрезков этого массива, которые являются стек-уничтожимыми.
Обратите внимание, что вам нужно ответить на \(q\) независимых запросов.
Выходные данные
На каждый запрос выведите одно число — количество стек-уничтожимых подотрезков массива \(a\).
Примечание
В первом запросе есть четыре стек-уничтожимых подотрезка: \(a_{1 \ldots 4} = [2, 1, 1, 2], a_{2 \ldots 3} = [1, 1], a_{2 \ldots 5} = [1, 1, 2, 2], a_{4 \ldots 5} = [2, 2]\).
Во втором запросе только один стек-уничтожимый подотрезок — \(a_{3 \ldots 4}\).
В третьем запросе есть восемь стек-уничтожимых подотрезков: \(a_{1 \ldots 8}, a_{2 \ldots 5}, a_{2 \ldots 7}, a_{2 \ldots 9}, a_{3 \ldots 4}, a_{6 \ldots 7}, a_{6 \ldots 9}, a_{8 \ldots 9}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
2 1 1 2 2
6
1 2 1 1 3 2
9
3 1 2 2 1 6 6 3 3
|
4
1
8
|