题目描述

科创建造活动里，小珅搭建了一排共$n$座特斯拉电磁塔，电塔从左到右依次编号$1 \sim n$，第$i$座电塔的高度为$h[i]$。小泽负责验收筛选美观的保留方案：可以选取部分电塔让其余电塔沉降地下，若留在地面的电塔按原有从左到右顺序排列后，高度能构成等差数列，这个选取方案就判定为美观。现在需要统计所有合法美观方案的总数，结果对指定模数取余。

美观方案判定细则：

1. 仅保留1座或2座电塔的方案，天然满足美观要求；完全不保留任何电塔的方案不算美观；
2. 形成的等差数列公差可以是正数、负数，也可以为0。

请求出所有美观选取方案的总数量，答案对$998244353$取模。

输入格式

第一行输入一个正整数$n$；

第二行输入$n$个非负整数，依次表示第$1$到第$n$座电塔的高度$h[i]$。

输出格式

输出一个整数，代表美观方案总数对$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

说明/提示

记$v$为所有电塔的最大高度：

• 前30%测试数据：$n \le 20$；
• 前60%测试数据：$n \le 100,\ v \le 2 \times 10^3$；
• 额外20%测试数据：整排电塔原始高度本身就是等差数列；
• 100%测试数据：$n \le 10^3,\ v \le 2 \times 10^4$。

1
0

1