Chef has a sequence A of 2 \cdot N integers containing all natural numbers from 1 to N exactly twice.

Let a sequence B containing K elements be a [subsequence] of A. We define a strictly increasing *index* sequence I(B) = [I_{1}, I_{2}, \ldots, I_{K}] such that, B can be written as [A_{I_{1}}, A_{I_{2}}, \ldots, A_{I_{K}}].
 
A pair of subsequences (P,Q) is said to be *good* if all of the following conditions satisfy:
Both subsequences have the same length. In other words, |P| = |Q|, where |P| and |Q| denote the lengths of P and Q respectively; 
The subsequences P and Q are disjoint. In other words, there are no common elements between I(P) and I(Q);
The subsequences are equal. In other words, P_{j} = Q_{j} for all (1≤ j ≤ |P|).

Find the total number of distinct ordered pairs of subsequences (P,Q) that are *good*.  
Two ordered pairs (P_{1}, Q_{1}) and (P_{2}, Q_{2}) are considered different iff I(P_{1}) \ne I(P_{2}) or I(Q_{1}) \ne I(Q_{2}).

Since the answer can be very large, print it modulo 998244353.

------ Input Format ------ 

- First line contains T − the number of test cases. The description of the test cases is as follows.
- The first line of each test case contains a single integer N − the value of N.
- The second line of each test case contains 2 \cdot N integers A_{1}, A_{2}, \ldots, A_{2 \cdot N}​. 

------ Output Format ------ 

For each test case, output a single integer − the total number of distinct ordered pairs of subsequences (P,Q) that are *good* modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 2\cdot 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $6\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
1
1 1
2
1 1 2 2
2
1 2 1 2
----- Sample Output 1 ------ 
2
8
6
----- explanation 1 ------ 
Test case $1$: Possible ordered pairs are: $([A_{1}], [A_{2}])$, $([A_{2}], [A_{1}])$.

Test case $2$: Possible ordered pairs are: $([A_{1}],[A_{2}])$, $([A_{2}], [A_{1}])$, $([A_{3}], [A_{4}])$,  $([A_{4}], [A_{3}])$, $([A_{1}, A_{3}], [A_{2}, A_{4}])$, $([A_{2}, A_{4}], [A_{1}, A_{3}])$, $([A_{1}, A_{4}], [A_{2}, A_{3}])$, $([A_{2}, A_{3}], [A_{1}, A_{4}])$.

Source: codechef | Difficulty: VERY_HARD
Tags: Combinatorics

Range queries

Segment trees revisited

Dynamic programming

Mathematics

Data structures


Solutions:
mod = 998244353

class FenwickTree:

	def __init__(self, x):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * (2 * n + 1)
	mark = [0] * (n + 1)
	other = [-1] * (n + 1)
	for i in reversed(range(2 * n)):
		if other[a[i]] == -1:
			other[a[i]] = i
	F = FenwickTree([0 for _ in range(2 * n + 5)])
	(before, ans) = (1, 0)
	for x in a:
		if mark[x] == 1:
			F.update(other[x], -dp[x] % mod)
			before += dp[x]
			before %= mod
		else:
			mark[x] = 1
			dp[x] = 2 * before + F.query(other[x])
			ans += dp[x]
			F.update(other[x], dp[x] % mod)
			ans %= mod
	print(ans)