题目描述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

提示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]).

出题Author

Staginner

来源Source