解题思路

核心改法：先做标准 LIS 分层，只在“能位于某条 LIS 上”的位置里连边，然后在相邻层之间用“值严格递增 + 位置可衔接”的条件建图，最后在“值节点”上做 DP，并且在每一层对相同数值合并（去重）。

具体步骤：

1. 计算每个位置 i 的

   • L[i]：以 a[i] 结尾的 LIS 长度（从左到右、值严格小于）。

题目内容

给定一个长度为$n$的数组$a$，请你计算其中所有本质不同最长上升子序列的数量。由于答案可能非常大，请将结果对$998244353$取模后输出。

**[子序列]**如果一个序列可以通过删除原序列的若干(可能为零)元素得到，则称前者为后者的一个子序列。

**[上升序列]**我们称$s$为一个上升序列，当且仅当其中任意相邻元素满足$s_i<s_{i+1}$

**[本质不同序列]**若两个序列的长度不同，或在某一位置上的元素不同，则认为它们是不同的序列。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下:

第一行输入一个正整数$n(1≤n≤2·10^5)$，代表数组$a$的长度。

第二行输入$n$个正整数$a_1,a_2,...,a_n (1≤a_i≤10^9),$代表$a$中的元素。

除此之外，保证单个测试文件的n之和不超过$2×10^5$。

输出描述

对于每组测试数据，输出一行一个整数，代表数组$a$中本质不同 最长上升了序列的数量，对$998244353$取模后的结果。

样例1

输入

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

输出

1
1
1
4
2

说明

在最后一组测试数据中，两个本质不同最长上升子序列分别为{$1,9$}和{$1,8$}