题目内容

有 $T$ 组数据。每组给定一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，保证其中元素互不相同，且每个 $a_i$ 满足 $1 \le a_i \le n$。 称区间 $[l, r]$ 是一个排列区间，当且仅当其中的数 $a_l, a_{l+1}, \ldots, a_r$ 恰好构成某个长度的排列：即存在正整数 $k$，使得这些数是 $1$ 到 $k$ 各出现一次。 请对每组数据求出排列区间的个数。

约束条件：

• $1 \le T \le 2$。
• 所有数据的 $n$ 之和不超过 $2 \times 10^5$。
• 对 $90\%$ 的测试点有 $T = 1$ 且 $n \le 2 \times 10^5$。