Валерий очень интересуется магией. Магия настолько его привлекает, что он видит её повсюду. Любые странные и непонятные явления он объясняет вмешательством потусторонних сил. Но кто бы мог подумать, что даже в обыкновенном массиве чисел Валера умудрится заметить что-то прекрасное и магическое.
Совершенно случайным образом к Валере попал кусок старинного пергамента, на котором был записан массив чисел. Он сразу же подумал, что числа в этом массиве вовсе не случайные. В результате продолжительных исследований Валера вывел чудесное свойство, которым должен обладать магический массив: массив называется магическим, если в нем минимум и максимум совпадают.
Этим своим знаменательным открытием он решил поделиться с вами, но взамен попросил о помощи. Несмотря на потрясающий ум и смекалку, Валера очень плохо считает и поэтому вам придется довести его работу до конца. Все, что от вас требуется, это посчитать количество магических подмассивов исходного массива чисел, записанных на пергаменте. Подмассивом будем называть непустую последовательность подряд идущих элементов.
Выходные данные
В единственной строке выведите ответ на задачу: количество подмассивов, являющихся магическими.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).
Примечание
Комментарии к примерам из условия:
Подходящие подмассивы обозначим в виде пары индексов [a;b] начала и конца.
В первом примере такими являются [1;1], [2;2], [3;3], [4;4], [2;3].
Во втором — [1;1], [2;2], [3;3], [4;4], [5;5], [1;2], [2;3], [1;3].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 1 4
|
5
|
|
2
|
5
-2 -2 -2 0 1
|
8
|