Background

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.

Problem Description

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.

Input Format

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 Format

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

8
13 14 6 20 27 34 34 41 

50

100
90 1004 171 99 1835 108 81 117 141 126 135 144 81 153 193 81 962 162 1493 171 1780 864 297 180 532 1781 189 1059 198 333 1593 824 207 1877 216 270 225 1131 336 1875 362 234 81 288 1550 243 463 1755 252 406 261 270 279 288 1393 261 1263 297 135 333 872 234 881 180 198 81 225 306 180 90 315 81 81 198 252 81 297 1336 1140 1238 81 198 297 661 81 1372 469 1132 81 126 324 333 342 81 351 481 279 1770 1225 549 

11153

Hint

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