1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#define maxn 300010
using namespace std;
const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
int n, a[maxn];
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
struct node {
int v, vf, vg;
int cf, cg;
} T[maxn * 4]; int pre[maxn];
inline void maintain(int i) {
T[i].vf = add(T[lc].vf, T[rc].vf);
T[i].vg = add(T[lc].vg, T[rc].vg);
T[i].v = add(T[lc].v, T[rc].v);
}
inline void Update_f(int i, int l, int r, int cf) {
T[i].cf = cf;
if (!cf) T[i].v = T[i].vf = 0;
else T[i].vf = add(pre[r], p - (l ? pre[l - 1] : 0)), T[i].v = T[i].vg;
}
inline void Update_g(int i, int l, int r, int cg) {
T[i].cg = cg;
if (!cg) T[i].v = T[i].vg = 0;
else T[i].vg = add(pre[r], p - (l ? pre[l - 1] : 0)), T[i].v = T[i].vf;
}
inline void pushdown(int i, int l, int r) {
int &cf = T[i].cf, &cg = T[i].cg, m = l + r >> 1;
if (~cf) Update_f(lc, l, m, cf), Update_f(rc, m + 1, r, cf);
if (~cg) Update_g(lc, l, m, cg), Update_g(rc, m + 1, r, cg);
cf = cg = -1;
}
void build(int i, int l, int r) {
T[i] = { 0, 0, 0, -1, -1 };
if (l == r) return ; int m = l + r >> 1;
build(lc, l, m); build(rc, m + 1, r);
maintain(i);
}
void update_f(int i, int l, int r, int L, int R, int f) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return Update_f(i, l, r, f);
int m = l + r >> 1; pushdown(i, l, r);
update_f(lc, l, m, L, R, f); update_f(rc, m + 1, r, L, R, f);
maintain(i);
}
void update_g(int i, int l, int r, int L, int R, int g) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return Update_g(i, l, r, g);
int m = l + r >> 1; pushdown(i, l, r);
update_g(lc, l, m, L, R, g); update_g(rc, m + 1, r, L, R, g);
maintain(i);
}
void query(int i, int l, int r, int k) {
if (l == r) return cout << T[i].v << " " << T[i].vf << " " << T[i].vg << "\n", void();
int m = l + r >> 1; pushdown(i, l, r);
if (k <= m) query(lc, l, m, k);
else query(rc, m + 1, r, k);
}
} T[2];
int f[maxn];
void work() {
cin >> n; stack<int> s, t;
for (int i = 1; i <= n; ++i) cin >> a[i];
T[0].build(1, 0, n); T[1].build(1, 0, n);
for (int i = 0; i <= n; ++i) T[0].pre[i] = T[1].pre[i] = 0;
T[0].pre[0] = 1; T[1].pre[0] = 0; f[0] = 1;
s.push(0); t.push(0);
for (int i = 1; i <= n; ++i) {
while (s.top() && a[s.top()] > a[i]) s.pop();
T[0].update_f(1, 0, n, s.top(), i - 1, ~i & 1);
T[1].update_f(1, 0, n, s.top(), i - 1, i & 1);
s.push(i);
while (t.top() && a[t.top()] < a[i]) t.pop();
T[0].update_g(1, 0, n, t.top(), i - 1, i & 1);
T[1].update_g(1, 0, n, t.top(), i - 1, ~i & 1);
t.push(i);
f[i] = add(T[0].T[1].v, T[1].T[1].v);
T[0].pre[i] = T[0].pre[i - 1]; T[1].pre[i] = T[1].pre[i - 1];
T[i & 1].pre[i] = add(T[i & 1].pre[i], f[i]);
} cout << f[n] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|