Beautiful Tesla Towers Selection

You are given n Tesla electromagnetic towers placed in a row, numbered from \(1\) to \(n\). The height of the \(i\)-th tower is \(h[i]\). A master builder has the ability to sink some of these towers underground. The towers that remain on the ground will form a sequence according to their original left-to-right order.

A selection is called beautiful if the heights of the towers left on the ground form an arithmetic progression. Note that if there is only one tower or two towers left on the ground, the resulting sequence is automatically considered an arithmetic progression. However, a selection where no tower remains on the ground is not considered beautiful. The common difference of the arithmetic progression may be negative, zero, or positive.

Your task is to count the number of beautiful selection schemes modulo \(998244353\). In other words, if you let \(S\) be a nonempty subset of \(\{1,2,\dots,n\}\) representing the indices of towers that remain on the ground, count how many subsets \(S\) satisfy that if \(|S| \ge 3\), there exists an integer \(d\) such that for the sorted indices \(i_1, i_2, \dots, i_k\) of \(S\), we have \[ h[i_2]-h[i_1] = h[i_3]-h[i_2] = \dots = d. \]

Hint: All one-tower and two-tower selections are beautiful, and for longer sequences you can use dynamic programming over the indices to count arithmetic subsequences.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) \( (1 \le n) \).
• The second line contains \(n\) space-separated integers \(h[1], h[2], \dots, h[n]\) representing the heights of the towers.

outputFormat

Output a single integer: the number of beautiful selection schemes modulo \(998244353\).

sample

3
1 2 3

7