#F8. 连续段

连续段

T4 连续段(consecutive)

时间限制:2.0 秒 空间限制:256 MB

题目描述

给定一个 11 到 nn 的排列 a1,a2,…,ana_1,a_2,\dots,a_n。

称一个子数组 al,al+1,…,ara_l,a_{l+1},\dots,a_r 是连续段,如果这个子数组中的最大值与最小值之差恰好等于 r−lr-l。由于排列中的数互不相同,这等价于这些数恰好构成一段连续的整数。

对每个 k=1,2,…,nk=1,2,\dots,n,请你求出前 kk 个数 a1,a2,…,aka_1,a_2,\dots,a_k 中连续段的数量。注意,连续段必须完全位于前缀内部。

输入格式

第一行一个正整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n,保证是 11 到 nn 的一个排列。

输出格式

输出 nn 行,第 kk 行表示前缀 a1,a2,…,aka_1,a_2,\dots,a_k 中连续段的数量。

样例 1

输入:

4
2 1 4 3

输出:

1
3
4
7

样例 1 解释:

  • 前缀 [2][2]:连续段为 [2][2],共 11 个;
  • 前缀 [2,1][2,1]:连续段为 [2],[1],[2,1][2],[1],[2,1],共 33 个;
  • 前缀 [2,1,4][2,1,4]:新增 [4][4],共 44 个([1,4][1,4] 和 [2,1,4][2,1,4] 都不是连续段);
  • 前缀 [2,1,4,3][2,1,4,3]:新增 [3],[4,3],[2,1,4,3][3],[4,3],[2,1,4,3],共 77 个。

样例 2

输入:

3
3 1 2

输出:

1
2
5

样例 2 解释: 前缀 [3][3] 有 11 个连续段;前缀 [3,1][3,1] 有 [3],[1][3],[1] 两个;前缀 [3,1,2][3,1,2] 新增 [2],[1,2],[3,1,2][2],[1,2],[3,1,2],共 55 个。

数据范围

对于全部测试数据:1≤n≤3×1051\le n\le 3\times 10^5;保证 aa 是 11 到 nn 的排列。

子任务

子任务 分值 特殊限制
1 20 n≤5000n\le 5000
2 排列单调递增或单调递减
3 n≤105n\le 10^5
4 40 无特殊限制

提示: 答案最大可达 n(n+1)2\frac{n(n+1)}{2},请使用 6464 位整数。