Value sequence ＜ detailed explanation of daily question ＞

subject ：

---

  Topic link ：

Sign in — major IT Written interview preparation platform _ Cattle from Niuke.com is the magic weapon of Internet Job Hunting ,C++、Java、 front end 、 product 、 Operational skills learning / Test preparation / Job search question bank , Online Baidu Alibaba Tencent Netease and other Internet famous enterprises written interview simulation test practice , Discuss the classic test questions with Niu Ren , Improve your technical ability in an all-round way https://ac.nowcoder.com/acm/contest/23481/B

---

Ideas ：

To do this problem, we must first understand a rule ：

Here's the picture

  Then we can discuss it in these two cases

Be the first 1 In this case ：

Its number of schemes is         2 Of i-j+1 Power

Be the first 2 In this case ：

Its number of schemes is         2 Of i-j+1 Power -1（ Remove the case of completely deleting the intermediate value ）

Then why is the number of schemes 2 Of i-j+1 Power Well ？

as follows

---

  Code details ：

#include<stdio.h>
#include<iostream>
using namespace std;
typedef  long long ll;
ll a[(ll)2e5 + 6];
const int mod = 998244353;
ll qsm(ll x, ll y)// Fast power 
{
	ll ans = 1;
	while (y)
	{
		if (y & 1) ans =ans*x%mod;
		y =y>> 1;
		x = x*x%mod;
	}
	return ans;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;	scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

		ll ans = 1;
		for (int i = 1; i <= n; i++)
		{
			int j = i;// Record the middle starting position 
			while (a[j + 1] == a[i]&&j<n) j++;// Take have 
			if (i >= 2 &&j<n&& ((a[j + 1]>a[i] && a[i]>a[i - 1]) || ((a[i] < a[i - 1]) && a[j + 1] < a[i])))
			{
				ans =  ans*qsm(2, j - i + 1)%mod;
			}// When satisfied i-1 To j+1 When the number in the range is single increase or single decrease （ And there can be equality in the middle ）, Then for the case that all equal numbers can be deleted 
			else
			{// The value in the middle is greater than the value on both sides or less than the value on both sides （ In this case, all intermediate values cannot be deleted ）  And i be equal to 1 The situation of 
				ans =ans* (qsm(2, j - i+1)-1)%mod;
			}
			i = j;// Perform the next interval query 
		}
		printf("%lld\n", ans);
	}
	return 0;
}

---

PS: Dew from tonight white , The moon is my hometown .____ Du Fu 《 On a moonlit night, I remember my brother 》