注意到数据范围很小，我们直接枚举每个数 $a_i$ 最后的值 $\le a_k$ 的方案数。

把 $\le a_k$ 的数标记成 $1$，$>a_k$ 的数标记成 $0$。

每次枚举各种更新方案，进行递推。

然后嗯 dp 就完了。

简单来说，假设我们目前从源点最多向左 $a$ 向右 $b$ 范围内均为 $1$，而向左共有 $x$ 个数，向右共有 $y$ 个数。

显然 $x+y=n-1$，$0\le a\le x$，$0\le b\le y$。

假设经过 $q$ 轮，这样的方案数为 $f_{q,a,b}$。

那么我们有

$$f_{q,a,b}\leftarrow(\binom{a+b+2}{2}+\binom{x-a+1}{2}+\binom{y-b+1}{2})f_{q-1,a,b} $$$$f_{q,a,t}\leftarrow(y-b)f_{q-1,a,b}\quad(0\le t<b) $$$$f_{q,t,b}\leftarrow(x-a)f_{q-1,a,b}\quad(0\le t<a) $$

容易使用前缀和优化，单轮复杂度 $O(n^2q)$。

对于同一对 $x,y$，也就是同一个源点，容易发现只用做一次 dp 即可记录所有信息；把 $a_k$ 带权压在一起即可。

由于要做 $O(n)$ 轮，总复杂度即为 $O(n^3q)$。

这个看上去非常过不去。

考虑改一下状态，不对每个元素 dp，而直接对全局 dp。

假设 $f_{q,l,r}$ 表示 $[l,r)$ 所有元素为 $1$，$l-1,r$ 均为 $0$ 的带权方案数。总区间为 $[0,n)$。

那么我们有

$$f_{q,l,r}\leftarrow(\binom{l+1}{2}+\binom{r-l+1}{2}+\binom{n-r+1}{2})f_{q-1,l,r} $$$$f_{q,l,t}\leftarrow(n-r)f_{q-1,l,r}\quad(l<t<r)$$ $$f_{q,t,r}\leftarrow lf_{q-1,l,r}\quad(l<t<r)$$

使用前缀和同样可以优化到 $O(n^2q)$。

最后每个点的总答案为包含其的区间的答案相加。

唯一的问题在于如何带权。

注意到我们每次计算出的结果相当于是给 $\le a_k$ 的方案数带了个权值，假设 $v_1\le v_2\le\dots\le v_n$，那么对于 $\le v_k$ 的方案数，其权值可以设为 $v_k-[k<n]v_{k+1}$，这样每种权值恰好被计算了正确的次数。

参考代码。