考虑设 $f_i$ 为前缀最大值比 $i$ 大的数量，那么显然答案就是 $\sum\limits_{i=1}^n f_i$。

考虑将选择 $1,-1$ 转化为 $(1,1),(1,-1)$ 的位移，所以根据题目要求从 $(0,0)$ 出发必须以 $(n+m,n-m)$ 作为终点。

比如下图就对应了 $\{1,−1,1,1,−1,−1,−1,1\}$ 这个序列：

那么如果一个路径想要给 $f_i$ 贡献答案，那么就一定需要经过 $y=i$ 这个常值函数函数才可以。

如果如果 $i\le n-m$ 也就是起点与终点的函数的异侧就一定会相交，所以 $f_i={n+m\choose n}$。

如果 $i\gt n-m$，那么就把起点从 $(0,0)$ 翻转到 $(2\times i,0)$ 就与上一种情况一样了，所以 $f_i={n+m\choose n-i}$。

放一张图辅助理解：