Read the former half first.

In fact, a sequence \(a=(a_1,a_2,\dots,a_k)\) with distinct elements is kadomatsu-like if and only if:

• \(a_1 < a_2\) and \(a_{k-1}>a_k\).

Proof

Let us define:

• a position where \(a_{i-1} < a_i\) and \(a_i > a_{i+1}\) as an \(x\)-turnover, and
• a position where \(a_{i-1} > a_i\) and \(a_i < a_{i+1}\) as a \(y\)-turnover.

If \(a_k < a_{k+1}\) for some \(k\), then the next turnover will always be an \(x\)-turnover.
Conversely, if \(a_k > a_{k+1}\) for some \(k\), then the next turnover will always be a \(y\)-turnover.

If \(a_1 < a_2\), there will be \(x\)-turnover, \(y\)-turnover, …, and so on, in this order. If \(x>y\), we should finish with an \(x\)-turnover without having a \(y\)-turnover, that is, \(a_{k-1} > a_k\), and this is sufficient.
If \(a_1 > a_2\), there will be \(y\)-turnover, \(x\)-turnover, …, and so on, where \(x>y\) never occurs.

This finishes the proof of the initial claim.

All that left is to count kadomatsu-like subsequences.

Fix the values of \(a_2\) and \(a_{k-1}\).
Suppose that there are \(p\) ways to take \(a_1\) such that \(a_1 < a_2\), and \(q\) ways to take \(a_k\) with \(a_{k-1} > a_k\).
To take into account the case where \(k=3\) (that is, \(k-1=2\)), add \(pq\) to the answer.
For cases where \(k \ge 4\), if \(a_2\) is \(P_l\) in the original sequence, and \(a_{k-1}\) is \(P_r\), then we can freely choose whether to use each of \(P_{l+1},P_{l+2},\dots,P_{r-1}\). Thus, add \(pq \times 2^{r-l-1}\) to the answer.
The number of ways to take \(a_1\) with \(a_1 < a_2\) and \(a_k\) with \(a_{k-1} > a_k\) can be counted using a data structure like a segment tree or a balanced binary search tree.
Summations with coefficients \(2^{r-l-1}\) can also be computed in the manner of cumulative sums.

This solution runs in \(O(N \log N)\) time.

Sample code (C++):

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

using namespace std;
using ll=long long;

const ll mod=998244353;

int main(){
  ll n;
  cin >> n;
  vector<ll> p(n);
  for(auto &nx : p){cin >> nx;}

  vector<ll> beg(n),fin(n);
  tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> tr;
  for(ll i=0;i<n;i++){
    beg[i]=tr.order_of_key(p[i]);
    tr.insert(p[i]);
  }
  tr.clear();
  for(ll i=n-1;i>=0;i--){
    fin[i]=tr.order_of_key(p[i]);
    tr.insert(p[i]);
  }

  ll res=0;
  for(ll i=0;i<n;i++){
    res+=beg[i]*fin[i];
    res%=mod;
  }
  ll s=0;
  for(ll i=0;i<n;i++){
    res+=s*fin[i];
    res%=mod;
    s=(2*s+beg[i])%mod;
  }
  cout << res << "\n";
  return 0;
}