Splitting Permutations into Arithmetic Progressions

Given a permutation \( p \) of the numbers \(1\) to \(n\), your task is to count the number of indices \( i \) (where \(1 \le i < n\)) such that when the permutation is split into two parts:

• The first part: \( [p_1, p_2, \cdots, p_i] \)
• The second part: \( [p_{i+1}, p_{i+2}, \cdots, p_n] \)

and each part is sorted in non-decreasing order, both resulting sequences form an arithmetic progression. Note that a sequence with one or two elements is always considered an arithmetic progression.

An arithmetic progression is defined as a sequence \( a_1, a_2, \cdots, a_k \) where for \( k \ge 3 \), the difference between consecutive elements is constant, i.e., \( a_{j+1} - a_j = d \) for every \( 1 \le j < k \). In \( \LaTeX \) format, this can be written as:

\( a_2 - a_1 = a_3 - a_2 = \cdots = a_{k} - a_{k-1} \).

inputFormat

The input consists of two lines.

• The first line contains a single integer \( n \) indicating the size of the permutation.
• The second line contains \( n \) space-separated integers \( p_1, p_2, \cdots, p_n \) representing the permutation of \( 1 \) through \( n \).

outputFormat

Output a single integer which is the count of indices \( i \) (\(1 \le i < n\)) such that after splitting and sorting both parts, each part forms an arithmetic progression.

sample

4
1 3 2 4

3