First observe the following lemma: a subsequence \((a_1, a_2, \dots, a_k)\) is kadomatsu-like iff \(a_1 < a_2\) and \(a_{k-1} > a_k\).

Proof: as all \(a_i\) are distinct, all such sequences can be decomposed into “ascending” and “descending” streaks. A “peak” is formed whenever an ascending streak turns into a descending streak , and a “valley” is formed whenever a descending streak turns into an ascending streak. Since a peak can only be followed by a valley and vice versa, the only way for the number of peaks to be greater than the number of valleys is if the sequence of turns both starts and ends with a peak, and this holds if and only if \(a_1 < a_2\) and \(a_{k-1} > a_k\).

We can thus calculate the answer by the following algorithm: Processing \(P_i\) by increasing \(i\), let \(\text{dp}[j]\) represent the number of subsequences that started with \(a_1 < a_2\) and ended with \(a_k = j\).

Also let \(C(i) = |\{ j: j < i \wedge P_j < P_i \}|\). Then:

\(\text{ans} \xleftarrow{+} \sum_{j > P_i} \text{dp}[j]\) (create subsequences that end in a descent to \(P_i\), then add them to the answer)

\(\text{dp}[P_i] \leftarrow C(i) + \sum_j \text{dp}[j]\) (count new sequences that start with an ascent, and also append \(P_i\) to all previous sequences)

Both \(\text{dp}\) and \(C(i)\) can be managed using a data structure that quickly handles range sums while allowing point updates, like a segment tree or Fenwick tree. The problem is thus solved in \(O(N \log N)\) time.