Валя был очень занят подготовкой контестов по программированию, поэтому ему теперь везде мерещатся задачи. Смотря на расписание автобусов, он видит массив из N чисел. Глядя на сидящих в автобусе людей, он замечает задачу на динамическое программирование. А на схеме маршрута он видит только неориентированный граф.

Даже в массиве чисел он видит графы. В спортивном программировании обычно используются простые неориентированные графы без петель и кратных рёбер. Такие графы, как правило, задаются массивом рёбер. Формально, граф из N вершин и M рёбер задаётся последовательностью из 2 + 2 · M целых чисел: сначала идёт число N, затем число M, затем M пар чисел, обозначающих рёбра. Каждое ребро задаётся номерами вершин, которые оно соединяет. Вершины нумеруются от 1 до N. В графе нет повторяющихся рёбер, а также нет рёбер, соединяющих одну вершину саму с собой. Граф из 0 вершин не считается корректным.

Вот и сейчас, посмотрев на массив из K чисел, Валя ищет там неориентированные графы, заданные именно таким форматом. Посчитайте, сколько непрерывных подпоследовательностей чисел в этом массиве задают граф вышеуказанным способом.

В первой строке дано целое число K — количество чисел в массиве (1 ≤ K ≤ 100 000).

Во второй строке дан массив из K целых неотрицательных чисел, записанных через пробел. Числа не превосходят 1 000 000 000.

Выведите целое число — количество подотрезков массива, которые задают корректный граф по правилам, описанным в условии.

В примере из условия есть три корректных записи графа: «2 1 1 2», «2 1 2 1» и «1 0». Первые две записи соответствуют графу с двумя вершинами и одним ребром, третья запись — пустому графу с одной вершиной.