Avoiding Arithmetic Progressions in a Sequence

Given an integer (n) and a sequence (S) of (n) integers, your task is to determine the minimal number of operations required such that no three consecutive elements form an arithmetic progression. In one operation, you may increment any one element by 1. Formally, for every index (i) with (0 \leq i \leq n-3), the condition

[ S[i+2]-S[i+1] \neq S[i+1]-S[i] ]

must hold. This problem requires careful handling of sequence modifications since altering one element might affect multiple triples. It is guaranteed that the answer exists for every valid input.

Example:
For (n=3) and (S=[1, 2, 3]), one operation (incrementing the middle element) transforms the sequence to ([1, 3, 3]), which does not contain any three consecutive terms forming an arithmetic progression. Thus, the minimal number of operations is 1.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n), representing the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence (S).

outputFormat

Print a single integer to standard output (stdout) indicating the minimal number of operations required to ensure that no three consecutive elements of the sequence form an arithmetic progression.## sample

3
1 2 3

1