P4933 Master.

The architecture master has recently been learning math from the math master ljt12138. Today, he learned arithmetic sequences, and ljt12138 decided to leave him an exercise.

ljt12138 first built $n$ Tesla electromagnetic towers. These towers are arranged in a line and numbered from left to right from $1$ to $n$. The height of the $i$-th tower is $h[i]$. The architecture master needs to choose some towers, and the chosen towers will shrink underground. At this time, if the heights of the towers that remain above ground form an arithmetic sequence from left to right, then this selection plan is considered beautiful. The architecture master needs to find how many beautiful selection plans there are in total, and output the answer modulo $998244353$. Note that if only one or two towers remain above ground, this plan is also considered beautiful. A plan where no tower remains above ground is considered not beautiful. Also note that the common difference of the arithmetic sequence can be negative.

The first line contains a positive integer $n$. The second line contains $n$ non-negative integers. The $i$-th integer is the height $h[i]$ of the $i$-th tower.

Output one integer, representing the number of beautiful plans modulo $998244353$.

Let $v$ be the maximum tower height. For the first $30\%$ of the testdata, $n \le 20$. For the first $60\%$ of the testdata, $n \le 100$, $v \le 2 \times 10^3$. For the other $20\%$ of the testdata, the heights of all towers form an arithmetic sequence. For $100\%$ of the testdata, $n \le 10^3$, $v \leq 2 \times 10^4$. Translated by ChatGPT 5