该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在一片神秘的果园中，生活着一只爱吃果子的聪明小猴子。果园的树上挂满了果子，这些果子按照固定的顺序排成一排，从左到右编号为 1 到 n 。每个果子的大小各不相同。小猴子按照果子的顺序依次走过，但它可以选择摘下某些果子，也可以不摘。

然而，果园的守护精灵有一个特殊的要求：小猴子摘取的所有果子必须满足以下条件，才能被视为合法采摘：

1. 摘下的任意三个果子中（假设编号为 x, y, z ，且满足 x < y < z，不能出现这样的大小关系：
   编号最小的果子 < 编号最大的果子 < 中间编号的果子。
   （例如，第 x 个果子是最小的，第 y 个果子是最大的，第 z 个果子是中等大小的，这样的采摘组合是不允许的！）

2. 同样的，摘下的任意三个果子中（假设编号为 x, y, z ，且满足 x < y < z，不能出现这样的大小关系：
   中间编号的果子 < 编号最大的果子 < 编号最小的果子。
   （例如，第 y 个果子是最小的，第 x 个果子是最大的，第 z 个果子是中等大小的，这样的采摘组合也不允许！）

问题描述

果园里共有 n 个果子，小猴子希望知道：在这些规则限制下，小猴子能选择的所有合法摘果子方式的数量。

1. 小猴子至少要摘取一个果子。
2. 所有的摘果方式需要保证摘取果子的顺序和果子编号顺序一致。
3. 结果需要对 998244353 取模。

一共有T组数据，对每组数据输出一个答案。

输入格式

• 第一行包含一个非负整数T, 表示测试数据组数。
• 每组数据第一行包含一个整数 n（$1 \leq n \leq 10^5$），表示果子的数量。
• 每组数据第二行包含 n 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$，互不相同），表示果子从左到右的大小。

输出格式

• 每组数据输出一行，表示所有合法摘果方式的数量，对 998244353 取模。

样例输入1

1
3
2 1 3

样例输出1

7

样例输入2

1
4
1 3 2 4

样例输出2

13

样例解释

对于输入的果子大小序列 [2, 1, 3]，其所有非空子序列中满足规则的摘果方式如下：

• [2]
• [1]
• [3]
• [2, 1]
• [2, 3]
• [1, 3]
• [2, 1, 3]

总共有 7 种合法摘果方式。

数据范围与约定

对于所有测试点，保证 $T\leq 20,n\leq 10^5$。保证 $p$ 是一个排列。

注意：本题输入文件较大，您可以使用这里提供的输入优化，或者使用自己的输入优化：

int rd(){
   char s=getchar();int v=0;
   while(s<'0'||s>'9')s=getchar();
   while(s>='0'&&s<='9')v=v*10+s-'0',s=getchar();
   return v;
}