1107 : Arithmetic Sequence

Description

A sequence of numbers is said to be arithmetic if there is a constant difference between successive elements.

Given an array of integers, your task is to count the number of contiguous subarrays which can be rearranged to form an arithmetic sequence.

Input

There will be at most 200 test cases. Each case begins with one integer n(1 ≤ n ≤ 10⁵), the length of the array. The next line contains n integers, denoting the array. The array is a permutation of values 1, 2, …, n. The size of the whole input file does not exceed 2MB.

Output

For each test case, print the number of contiguous subarrays which can be rearranged to form an arithmetic sequence.

Sample

3
2 3 1
4
1 4 2 3

6
9

Hint

For the second sample, the following 9 subarrays can be rearranged to form an arithmetic sequence: [1], [4], [2], [3], [1, 4], [4, 2], [2, 3], [4, 2, 3] (→ [2, 3, 4]), [1, 4, 2, 3] (→ [1, 2, 3, 4]).

Source

Author

Staginner