Code

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

const int inf = (int)1e9 + 7;
const int mod = 998244353;

void add(int &a, int b) {
    a += b;
    a %= mod;
}

int solve(vector<int> &a) {
    int n = a.size();

    // dp[i] is the number of reachable arrays of a[0...i] that necessarily
    // end at the i-th element.
    // Note that dp[i] completelty ignores the element to the right of 'i'.
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
        int suff_min = inf;
        // Case 1: The last second element is a[j] and we append a[i] at the
        // end. This can happen only if all the elements in the range
        // [j + 1 .... i - 1] are absorbed either by a[i] or a[j].
        for (int j = i - 1; j >= 0; j--) {
            suff_min = min(suff_min, a[j]);
            int absorber = min(a[i], a[j]);
            if (absorber <= suff_min) {
                add(dp[i], dp[j]);
            }
        }

        // Case 2 : a[i] is the only element remaining.
        // This happens only when a[i] can absorb all elements to the left.
        suff_min = min(suff_min, a[i]);
        if (suff_min == a[i]) {
            add(dp[i], 1);
        }
    }

    int suff_min = inf, ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        suff_min = min(suff_min, a[i]);
        if (suff_min == a[i]) {
            add(ans, dp[i]);
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        cout << solve(a) << "\n";
    }

    return 0;
}

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

const int inf = (int)1e9 + 7;
const int mod = 998244353;

void add(int &a, int b) {
    a += b;
    a %= mod;
}

void sub(int &a, int b) {
    a -= b;
    a %= mod;
    if (a < 0) {
        a += mod;
    }
}

int query(vector<int> &pref, int l, int r) {
    if (l > r) {
        return 0;
    }
    int ans = pref[r];
    if (l > 0) {
        sub(ans, pref[l - 1]);
    }
    return ans;
}

int solve(vector<int> &a) {
    int n = a.size();

    // dp[i] is the number of reachable arrays of a[0...i] that necessarily
    // end at the i-th element.
    // Note that dp[i] completelty ignores the element to the right of 'i'.
    vector<int> dp(n), pref(n);
    stack<int> st;
    int dp_values_sum_on_stack = 0;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] > a[i]) {
            sub(dp_values_sum_on_stack, dp[st.top()]);
            st.pop();
        }

        if (st.empty()) {
            add(dp[i], 1 + (i ? pref[i - 1] : 0));
        } else {
            dp[i] = dp_values_sum_on_stack;
            add(dp[i], query(pref, st.top() + 1, i - 1));
        }

        pref[i] = i ? pref[i - 1] : 0;
        add(pref[i], dp[i]);
        st.push(i);
        add(dp_values_sum_on_stack, dp[i]);
    }

    int suff_min = inf, ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        suff_min = min(suff_min, a[i]);
        if (suff_min == a[i]) {
            add(ans, dp[i]);
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        cout << solve(a) << "\n";
    }

    return 0;
}