Valya was very busy preparing programming contests, so now he sees problems everywhere. Looking at the bus schedule, he sees an array of N numbers. Looking at the people sitting on the bus, he notices a dynamic programming problem. And on the route map, he sees only an undirected graph.

Even in an array of numbers, he sees graphs. Simple undirected graphs without loops and multiple edges are usually used in competitive programming. Such graphs are usually represented by an array of edges. Formally, a graph with N vertices and M edges is represented by a sequence of 2 + 2 · M integers: first comes the number N, then the number M, then M pairs of numbers representing the edges. Each edge is represented by the numbers of the vertices it connects. The vertices are numbered from 1 to N. The graph does not have duplicate edges, and there are no edges connecting a vertex to itself. A graph with 0 vertices is not considered valid.

Now, looking at an array of K numbers, Valya is looking for undirected graphs represented in this format. Count how many continuous subsequences of numbers in this array represent a graph according to the rules described above.

The first line contains an integer K — the number of numbers in the array (1 ≤ K ≤ 100 000).

The second line contains an array of K integers, non-negative, separated by spaces. The numbers do not exceed 1 000 000 000.

Print an integer — the number of subarrays in the array that represent a valid graph according to the rules described in the problem statement.

In the example from the problem statement, there are three valid graph representations: «2 1 1 2», «2 1 2 1» and «1 0». The first two representations correspond to a graph with two vertices and one edge, and the third representation corresponds to an empty graph with one vertex.