极端扩展

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

对于一个正整数数组 $b$，定义一次操作为：选择一个下标 $i$，把 $b_i$ 替换为两个正整数 $x,y$，其中 $x+y=b_i$。

数组的极端值定义为：把数组变成非递减数组所需的最少操作次数。可以证明任意正整数数组都能通过有限次操作变为非递减。

给定数组 $a$，求它所有非空连续子数组的极端值之和。相同内容的子数组如果出现在不同位置，也要分别计数。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试输出一个整数，表示所有非空连续子数组的极端值之和对 $998244353$ 取模的结果。

样例输入 1

1
3
5 4 3

样例输出 1

5

数据范围

$1\le t\le10000$，$1\le n\le100000$，$1\le a_i\le100000$；所有测试组的 $n$ 之和不超过 $100000$。