电子带负电

Problem Description

2025/7/27 经过激烈的讨论，我们认为电子应当带负电。因此，给此题中的序列添加 负数 的提案被严肃驳回，因为这些负号被电子夺走了。电子好闪，拜谢电子！ 给定一个长度为 $n$ 的 非负整数 序列 $a_1,a_2,a_3,\cdots,a_n$。 定义函数 $f\ (l,r,L,R)$，其中 $l,r,L,R$ 均为整数，$1\le l\le r\le n$，$-n\le L\le R\le n$。其值根据以下方法得到：

1. 将所有满足 $l\le i\le r$（$i$ 是整数）且 $L\le a_i\le R$ 的 $a_i$ 依照它们在 $a_1,a_2,a_3,\cdots,a_n$ 中的顺序取出，组成一个新序列 $b_1,b_2,b_3,\cdots,b_x$，其中 $x$ 为新序列的长度。
2. 若 $x>0$，则 $f\ (l,r,L,R)$ 的值为 $b$ 的最大子段和，否则 $f\ (l,r,L,R)=-\infty$。 求出函数 $f$ 的最大值。同时求出达到这个最大值的不同函数参数的组数对 $998244353$ 取模后的值。

Input

本题包含多组测试数据。 来自电子的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。 首先在第一行输入一个整数 $T$（$1\le T\le10$）表示测试数据组数。 对于每一组测试数据，输入包含两行。 第一行包含一个整数 $n$（$1\le n\le2\times10^5$）表示序列的长度。 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n$（$0\le a_1,a_2,a_3,\cdots,a_n\le n$）表示序列的元素。

Output

对于每一组测试数据，输出包含一行两个整数表示函数的最大值和达到它的不同函数参数组数对 $998244353$ 取模后的值。 注意：输出函数最大值时不应当进行取模。 对于每一组测试数据，可以证明函数 $f$ 的最大值均为非负整数。

Sample Input

2
3
0 2 1
5
0 0 0 0 0

Sample Output

3 20
0 540

Hint

在样例的第一组测试数据中，最大值为 $3$。满足 $l\le 2$，$r=3$，$L\le 1$，$R\ge 2$ 的函数参数均可达到最大值，结合函数的定义域可得组数为 $2\times1\times5\times2=20$。 在样例的第二组测试数据中，最大值为 $0$。满足 $L\le 0$，$R\ge 0$ 的函数参数均可达到最大值，结合函数的定义域可得组数为 $15\times6\times6=540$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）