题目描述

给定一列长度为 $m$ 的塔，高度为 $h_i$（第 $i$ 个塔）。 从左侧观看时，你能看到那些严格高于其左侧所有塔的塔；从右侧观看时，你能看到那些严格高于其右侧所有塔的塔。设对于一列高度序列 $h$：

• $L(h)$ 为从左侧能看到的高度的集合（按出现顺序），
• $R(h)$ 为从右侧能看到的高度的集合（按出现顺序）。

现在给出序列 $a_1,a_2,\dots,a_n$。求满足下面条件的子序列个数（不同子序列按选取的下标不同计为不同）：

• 对选出的任意子序列 $a'$，有 $L(a)=L(a')$ 且 $R(a)=R(a')$。

答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $t$（测试用例数）。 每个测试用例包含两行：

• 第一行一个整数 $n$（长度），
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

对每个测试用例输出一行：满足条件的子序列个数，对 $998244353$ 取模。

样例输入

5
5
4 2 4 8 3
5
1 2 3 2 1
6
1 2 3 3 2 1
9
3 5 5 7 4 6 7 2 4
1
10

样例输出

5
1
3
51
1

说明

样例解释

在第一个示例中， $L(a) = \{4, 8\}$ ， $R(a) = \{3, 8\}$ 。答案中包含的子序列是

• $[4, 8, 3]$ （第 $1$ 、 $4$ 、 $5$ 个 元素）；
• $[4, 8, 3]$ （第 $3$ 、 $4$ 、 $5$ 个元素）；
• $[4, 2, 8, 3]$ （ 第 $1$ 、 $2$ 、 $4$ 、 $5$ 个元素）；
• $[4, 4, 8, 3]$ （ 第 $1$ 、 $3$ 、 $4$ 、 $5$ 个元素）；
• $[4, 2, 4, 8, 3]$ （整个序列）。

在第二个例子中，唯一有效的子序列就是给定序列本身。

数据范围

• $1\le t\le 100$，
• $1\le n\le 5000$，
• 所有测试用例中 $n$ 的总和不超过 $5000$。
• 每个 $a_i$ 满足 $1\le a_i\le 10^9$。