Count Arithmetic Sequences in an Array

You are given an array of integers. Your task is to count the number of contiguous arithmetic subsequences in the array with length at least 3. An arithmetic sequence is a sequence of numbers such that the difference between consecutive elements is constant. Formally, given an array \(a_1, a_2, \dots, a_n\), count the number of pairs of indices \((i, j)\) with \(i + 2 \le j < n\) for which the subsequence \(a_i, a_{i+1}, \dots, a_j\) forms an arithmetic progression (i.e. \(a_{k+1} - a_k = d\) for all \(i \le k < j\)).

For example, for the array [1, 2, 3, 4], the valid arithmetic subsequences are:

• [1, 2, 3]
• [2, 3, 4]
• [1, 2, 3, 4]

Your task is to output the total number of such arithmetic sequences.

inputFormat

The input is given from standard input and consists of two lines:

1. The first line contains a single integer \(n\) \( (n \ge 1)\), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer to standard output: the number of contiguous arithmetic subsequences of length at least 3 in the array.

## sample

4
1 2 3 4

3

</p>