무작위 순열

$1$부터 $n$까지의 정수 $n$개로 이루어진 순열 $p$가 주어진다. 다음 연산을 $n$번 수행하여 $p$로부터 수열 $a$를 만든다.

• $p$의 최솟값을 $a$의 끝에 추가한다.
• $p$의 양 끝 중 왼쪽 또는 오른쪽 원소 하나를 제거한다.

주어지는 순열 $p$는 무작위로 생성된 순열이다. 위 방법으로 만들 수 있는 서로 다른 수열 $a$의 개수를 구하라. 개수가 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다. 두 수열은 값이 다른 위치가 하나라도 있으면 서로 다른 수열이다.

크기가 $n$인 순열은 $1$부터 $n$까지의 서로 다른 정수 $n$개로 이루어진 수열이다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 2 \cdot 10^5$)가 주어진다. 그 뒤로 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 순열의 크기 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어진다. 다음 줄에는 순열 $p$의 원소 $n$개가 주어진다. 순열은 의사 난수 생성기로 만들어진다.

모든 테스트 케이스의 $n$을 합하면 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 답을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.