Problem Background

The Architect is recently learning mathematics with the Math Master ljt12138. Today, he learned about arithmetic sequences, and ljt12138 decided to give him an exercise.

Problem Description

ljt12138 first built $n$ Tesla electromagnetic towers, which are arranged in a row, numbered from 1 to $n$ from left to right, with the height of the $i$-th tower being $h[i]$.

The Architect needs to select some of these towers, which will then sink into the ground. At this point, if the heights of the towers left on the ground, from left to right, form an arithmetic sequence, then this selection scheme is considered beautiful.

The Architect needs to find out how many beautiful selection schemes there are, the answer modulo $998244353$.

Note that if only one or two towers are left on the ground, this scheme is also considered beautiful. A scheme with no towers left on the 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, where the $i$-th integer is the height $h[i]$ of the $i$-th tower.

Output Format

Output an integer representing the number of beautiful schemes modulo $998244353$.

Sample Input and Output

Input Sample #1

8
13 14 6 20 27 34 34 41

Output Sample #1

50

Input Sample #2

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

Output Sample #2

11153

Notes

Let $v$ be the height of the tallest tower.

For the first $30\%$ of the data, $n \le 20$.

For the first $60\%$ of the data, $n \le 100$, $v \le 2 \times 10^3$.

For another $20\%$ of the data, the heights of all towers form an arithmetic sequence.

For $100\%$ of the data, $n \le 10^3$, $v \le 2 \times 10^4$.

见题面 Input 部分

见题面 Output 部分