首先对于一个 \(a\) 看看答案的形式长什么样子。
显然，如果 \(a_i \le a_j\)，那么 \([i, j]\) 中间的点要么和 \(i\) 连边要么和 \(j\) 连边，都是属于同一个连通块。
将这些 \([i, j]\) 合并，显然连通块都是连续的一段区间，但是合并过程不好考虑，我们考虑这些段的分界点，那么答案就是分界点个数加上总情况数。
考虑一个分界点要能满足条件，必须左边的所有数都大于右边的所有数，填入方案可以枚举值域上的分界点简单容斥一下。
最后做完了。
带来的启示是计数题要发现计数结构的性质，以及正难则反，拆贡献等经典套路。