对于一个序列和一个询问集合，设 $S_i$ 为包含了 $i$ 这个位置的询问的集合。一个询问集合合法当且仅当 $S_i$ 互不相同。
性质 1 ：如果 $a<b<c<d, S_a=S_c, S_b=S_d$，那么 $S_a=S_b=S_c=S_d$ 。
证明：包含了 $a$ 和 $c$ 的询问必然包含 $b$ ，而由于 $S_b=S_d$ ，所以也就必然包含了 $d$ 。其它情况同理。
性质 2 ：假设 $a$ 是序列中第一个其 $S_i$ 至少出现了两次的元素，$b$ 是 $S_a$ 最后一次出现的位置，那么询问集合中不存在区间与 $[a,b]$ 有交且不互相包含。
证明：对于一个与 $[a,b]$ 相交且不互相包含的区间，这个区间必然只包含了 $a,b$ 中的一个，于是推出 $S_a\neq S_b$ ，矛盾。
统计不合法的询问集合数量。对于一不合法的询问集合和一个序列，我们对 $\{S_i\}$ 进行如下的操作：
- 找到第一个出现了至少两次的 $S_i$ ，然后找到它最后一次出现的位置，设这两个位置是 $l,r$
- 将 $[l,r]$ 区间内的元素删掉，替换为一个 $S_i = S_l$ 的元素，并重复 1.
显然不会有与被删掉的区间有交但不包含的询问；所以确定“没有被包含于删掉了的区间的询问”的方案数就是把被删掉的区间换成一个点之后的合法的询问集合数；被包含在删除了的区间内部的询问可以任意地确定。
设表示 $f_i$ 序列长度为 $i$ 时，合法的询问集合的数量；设 $s_{i,j}$ 表示有 $i$ 个被删除的区间，其总长度为 $j$ ，确定被这些区间完全包含了的询问的方案数。计算 $f_i$ 的时候枚举被删掉的区间数量和长度总和即可。