As you may have guessed, Vadim loves solving as well as creating Sudoku with unusual rules. In this task, he will tell you about renban lines. This line can pass through any number of cells, and the values from these cells form a set of distinct consecutive integers in any order. For example, a line passing through 5 cells with values 4,7,5,3,6 forms a renban, while a line passing through 3 cells with values 2,1,8 does not form a renban.

This time, Vadim has created a sequence of N numbers and wants to place a renban line on it such that it passes through some consecutive cells (in other words, a subarray). Help him find the number of ways to do this.

The first line contains an integer N — the number of numbers in Vadim’s sequence (1 ≤ N ≤ 10⁵).

The second line contains N integers a_i — the numbers in the sequence in the order they are written (1 ≤ a_i ≤ 10⁵).

Output the number of ways to place a renban on the sequence.

In the example above, the renban line can pass through the cells of the subarrays [4], [4,2,3], [4,2,3,1], [2], [2,3], [2,3,1], [3], [3,1,2], [1], [1,2], [2].