[count] [combined number] value series

Topic link ：

https://ac.nowcoder.com/acm/contest/23481/B

---

Don't calculate the sequence a The value of , Because it is difficult to do it from this aspect .
Which values should be taken from the sequence to make the sequence a The value remains unchanged .

For three numbers to discuss ：

• $a_i<a_j<a_k$ or $a_i>a_j>a_k$ when
  Delete the number in the middle , The value of the sequence will not change . If the same number in the middle has k individual , The number of cases is $2^k$
• $a_i<a_j>a_k$ or $a_i>a_j<a_k$ when
  Delete the middle value , The value of the sequence will change , So you can't delete . But if there are multiple equal values in the middle , Leave at least one value . If the number of equal numbers is k, Then the number of cases is $2^k-1$( Remove the empty condition )

Next , Is to discuss the same number in the middle

Treat equal numbers as a connected block , Set to $[i,j]$

• If meet $a_{i-1}<a_i=...=a_j<a_{j+1}$ or $a_{i-1}>a_i=...=a_j>a_{j+1}$（ And to satisfy $i>1,j<n$）, Then interval $[i,j]$ The number of can be deleted completely , Does not affect the value , Such a range contributes a lot to the answer $2^{j-i+1}$ Kind of plan .
• Otherwise, the interval $[i,j]$ The number of must keep one , Such a range contributes to the answer $2^{j-i+1}-1$ Kind of plan . The answer is to multiply the contributions of all intervals .

---

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5 + 5, mod = 998244353;

vector<ll> fac(N);
void solve()
{
    
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &i : a) cin >> i;
	
	ll res = 1;
	for(int i = 0, j = 0; i < n; i++)	
	{
    
		j = i;
		while(j < n - 1 && a[j + 1] == a[i]) j++;
		
		if(i - 1 >= 0 and j + 1 < n and (a[i - 1] < a[i] && a[i] < a[j + 1] || a[i - 1] > a[i] && a[i] > a[j + 1]))
			res = res * fac[j - i + 1] % mod;
		else res = res * (fac[j - i + 1] - 1) % mod;
		i = j;
	}
	cout << res << "\n";
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	fac[0] = 1;
	for(int i = 1; i < N; i++) 
		fac[i] = fac[i - 1] * 2 % mod;
	int t;
	cin >> t;
// t = 1;
	while(t--) solve();
	return 0;
}