This contains a brief solution by the setter, a detailed editorial will be available by tomorrow.
Observation1: It is impossible that a local maximum becomes local minimum after some deletions, vice versa.(excluding edge elements)
Observation2: There are at most 4 valid operations for each move. 1. First element 2. second element 3. last element 4. second last element.
Solution:
Define pre[i][j] as the number of legal ways to delete the whole prefix(i) except the element with value = j, only using the first two operations. And also, define suf[i][j] as the symmetry definition. We will talk about the way to build these two arrays later. But here, we try to find the answer assuming we’ve already built them.
Let’s enumerate i from 2 to n - 1 and calculate the number of ways to delete the permutation, such that there exists a moment in the process that exactly 3 elements are left, a[i] and an element from prefix(i-1) and suffix(i+1) each. Note that the operations in the prefix and suffix will be independent, so the answer will be sum_of(pre[i-1][j < a[i]]) * sum_of(suf[i+1][j < a[i]]) * C(n-3,i-2) * (3!). (Assuming a[i] is bigger than its neighbors initially)
So now, the only problem left is to build arrays pre and suf in advance. It could be done with sweep-line trick + segment tree. The segment tree should support: Single point modify (adding value), range modify (resetting to zero), and prefix (or suffix) sum query.
Overall complexity: nlog(n).