598. Arithmetic Subarrays

0

Medium

Given an array of integers, an arithmetic subarray is defined as a contiguous subsequence of at least three elements where the difference between any two consecutive elements is the same. For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic subarrays. Given an integer array nums, determine the number of arithmetic subarrays it contains.

Input Format

The first line of input contains the size of the array. The second line contains the elements of the array separated by spaces.

Output Format

Print the number of arithmetic subarrays of nums as an integer.

Example

Input

4
1 2 3 4

Output

3

Constraints

1 <= nums.length <= 5000

-1000 <= nums[i] <= 1000

-1000 <= nums[i] <= 1000

Loading...

View Submissions

Console