我们构造新问题与原问题等价：

• 给定一个栈，按照值域扫描线，每次 Push。遇见某个 $A_i$ 可以 Pop 任意个数，如果此时栈空了，则称这次 Pop 是优秀的。
• 可以发现最后恰好 $k$ 次优秀 Pop 对应了原问题 $k$ 个 $x_i=A_i$ 的答案：将 Push 看成使 $A_i-x_i$ 加一即可。

考虑将问题反过来：

• 给定一个栈，按照值域扫描线，遇见某个 $A_i$ 就 Push。每次 Pop 任意个数。
• 可以发现最后栈中恰好剩下 $k$ 个数的方案数，对应了原问题 $k$ 个 $x_i=A_i$ 的答案：每次值域往下扫，就是将已经离栈的元素集体减一，并决定一些元素脱离上界。

exactly 太强了，改成 at least：因为反向问题中，最后一个肯定是 Pop。不妨将最后一步去掉，算 $\geq k$ 个元素的方案数。这个和 $\forall i\in[k+1, n],x_i< A_i$ 的所有合法方案一一对应：我们无非就是去掉了原先的最后 $k$ 个 Push。因为任意方案满足栈大小 $\geq 0$，所以加回 $k$ 个 Push 保证了栈大小 $\geq k$。

于是问题得到转化。剩下的问题考虑分治解决：看成一个表格，那么要统计的是底下的线上每个点，到右侧线上的路径数。我们考虑按照 $A_{mid}$ 分成三个部分，递归时给每个右侧线上点带一个系数（继续往后走的方案数）。

那么先递归右上侧，求答案。中间的部分通过卷积求出左侧线和底下的线的答案，系数是组合数。然后拿中间部分求出的左侧线答案，去递归左下侧即可。

时间复杂度 $O(n\log^2 n)$。