神题！！！！！！！！！/bx
全部格子都被覆盖不好处理，考虑钦定 \(k\) 个格子不被覆盖，容斥系数就是 \((-1)^k\)。
发现网格的行不一定连续，但是列是连续的。如果一列有格子被钦定，那么这一列就不能放棋子。
由此想到枚举不能放棋子的列（至少有一个棋子被钦定的列）集合 \(S\)，把每个行连续段的贡献相乘。
设行连续段有 \(len\) 个格子，其中 \(p\) 个格子所在列属于 \(S\)，那么如果这个行连续段没有格子被钦定，每个所在列不属于 \(S\) 的格子都能放棋子，贡献是 \(2^{len - p}\)；如果至少一个格子被钦定，枚举钦定了几个格子，得贡献为 \(\sum\limits_{i = 1}^p \binom{p}{i} (-1)^i = -[p > 0]\)。
但是很容易看出来一个问题，就是 \(S\) 中的列不一定至少有一个棋子被钦定。
仍然考虑容斥，钦定 \(T \subseteq S\) 为没有格子被钦定的列集合，容斥系数为 \((-1)^{|T|}\)；设行连续段中有 \(q\) 个格子所在列属于 \(T\)，那么如果这个行连续段没有格子被钦定，贡献仍然是 \(2^{len - p}\)；如果至少一个格子被钦定，贡献为 \(\sum\limits_{i = 1}^{p - q} \binom{p - q}{i} (-1)^i = -[p - q > 0] = -[p > q]\)。计算答案就把每个行连续段这样的贡献相乘即可。
枚举 \(S, T\) 复杂度显然过高，考虑简化。
首先我们发现只有连续段中 \(|S| = p, [|S| > |T|] = [p > q]\) 在计算贡献时有用。
然后考虑把网格按 \(h_i\) 的笛卡尔树剖分成若干个行连续段的贡献相同的形式，像这样（图来自 Verdandi）：
建出笛卡尔树，发现相邻的色块（父亲与儿子）相互依赖。比如上图，绿色块的 \(p\) 等于第 \(1, 3, 5\) 列是否被 \(S\) 包含加上橙色块的 \(p\) 加上黄色块的 \(p\) 加上粉色块的 \(p\)，同理，\([p > q]\) 是所有子结点的 \([p > q]\) 的或（或者可以维护 \([p = q]\)，就是所有子结点的 \([p = q]\) 的与）。
考虑一个树形 dp，\(f_{u, i, 0/1}\) 表示 \(u\) 结点目前 \(p = i\)，\([p = q] = 0/1\) 的容斥系数 \((-1)^{|T|}\) 乘贡献之和。我们首先考虑空行，也就是 \(f_{u, 0, 0} = f_{u, 1, 0} = 1, f_{u, 1, 1} = -1\)（对于 \(h_i\) 相同的子结点强制钦定一个父子顺序）。然后树形背包合并上来子结点。最后乘上若干行（设为 \(b_u\)）连续段的贡献，也就是 \((2^{sz_u - p} - [p > q])^{b_u}\)。
快速幂计算贡献是 \(O(n^2 \log n)\)，容易通过预处理这个贡献做到 \(O(n^2)\)。
code
// Problem: F - Histogram Rooks
// Contest: AtCoder - AtCoder Grand Contest 041
// URL: https://atcoder.jp/contests/agc041/tasks/agc041_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 410;
const int logn = 10;
const ll mod = 998244353;
ll n, a[maxn], stk[maxn], top, L[maxn], R[maxn], pw[maxn][maxn][2];
pii h[maxn][logn];
bool vis[maxn];
vector<int> G[maxn];
inline pii qmin(int l, int r) {
int k = __lg(r - l + 1);
return min(h[l][k], h[r - (1 << k) + 1][k]);
}
int build(int l, int r) {
if (l > r) {
return 0;
}
int mid = qmin(l, r).scd;
int p = build(l, mid - 1), q = build(mid + 1, r);
if (p) {
G[mid].pb(p);
}
if (q) {
G[mid].pb(q);
}
return mid;
}
ll f[maxn][maxn][2], sz[maxn], g[maxn][2], b[maxn];
inline void upd(ll &x, ll y) {
((x += y) >= mod) && (x -= mod);
}
void dfs(int u) {
sz[u] = 1;
f[u][0][1] = f[u][1][0] = 1;
f[u][1][1] = mod - 1;
for (int v : G[u]) {
b[v] = a[v] - a[u];
dfs(v);
for (int i = 0; i <= sz[u]; ++i) {
g[i][0] = f[u][i][0];
g[i][1] = f[u][i][1];
f[u][i][0] = f[u][i][1] = 0;
}
for (int i = 0; i <= sz[u]; ++i) {
for (int j = 0; j <= sz[v]; ++j) {
upd(f[u][i + j][1], g[i][1] * f[v][j][1] % mod);
upd(f[u][i + j][0], (g[i][1] * f[v][j][0] % mod + g[i][0] * (f[v][j][0] + f[v][j][1]) % mod) % mod);
}
}
sz[u] += sz[v];
}
for (int i = 0; i <= sz[u]; ++i) {
f[u][i][0] = f[u][i][0] * pw[sz[u] - i][b[u]][0] % mod;
f[u][i][1] = f[u][i][1] * pw[sz[u] - i][b[u]][1] % mod;
}
}
void solve() {
scanf("%lld", &n);
ll k = 1;
for (int i = 0; i <= n; ++i) {
pw[i][0][0] = pw[i][0][1] = 1;
for (int j = 1; j <= n; ++j) {
pw[i][j][0] = pw[i][j - 1][0] * (k + mod - 1) % mod;
pw[i][j][1] = pw[i][j - 1][1] * k % mod;
}
k = k * 2 % mod;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
h[i][0] = mkp(a[i], i);
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
h[i][j] = min(h[i][j - 1], h[i + (1 << (j - 1))][j - 1]);
}
}
int rt = build(1, n);
b[rt] = a[rt];
dfs(rt);
ll ans = 0;
for (int i = 0; i <= n; ++i) {
upd(ans, f[rt][i][0]);
upd(ans, f[rt][i][1]);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}