解题思路

我们要求的是“按数值区分”的 LIS（最长上升子序列）的条数：同一数值序列只算 1 次，即使出现位置不同。 关键观察：

• 把数组中每个不同的数值当作一个节点 $v$。设

  • $\text{minPos}[v]$ 为该值首次出现的位置；
  • $\text{maxPos}[v]$ 为该值最后出现的位置。

题目内容

给定一个长度为$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$}