#6725. 「CodePlus #7」六元环

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

qwqwq。


给定序列 a_0, a_1, \dots, a_n, a_{n+1} ;满足 a_0 = a_{n+1} = +\infty a_1, a_2, \dots, a_n 在输入中给出;

1\le x\le n ,称 \max_{0\le i<x, a_i\ge a_x} i x 是相邻的,且 \min_{x< i\le n+1, a_i>a_x} i x 相邻的;如果 x y 相邻,则 y x 也相邻;

如果 0 \le b_1, b_2, b_3, b_4, b_5, b_6\le n+1 ,且 b_i b_{i+1} 相邻, b_1 b_6 相邻, b_i 互不相同,则称集合 \{b_1,b_2,b_3,b_4,b_5,b_6\} 是一个六元环(即判断两个六元环是否相同时,不考虑 b_i 的顺序)。

共有 m 次修改操作,每次修改操作给出 x\ y ,将 a_x 改为 a_x + y ;每次修改后要求输出六元环的个数;

以上提到的所有数值为整数,且 1\le n, m\le 5\times 10^5, 1\le x\le n,1\le a_i, y\le 10^9

输入格式

第一行一个整数 n

第二行 n 个整数表示 a_1, a_2, \dots, a_n

第三行一个整数 m ;接下来 m 行,每行两个整数 x\ y 表示一次修改操作。

输出格式

m 行,每行一个整数,表示每次修改后的六元环个数。

样例

样例输入

6
1 2 5 4 3 6
4
1 8
3 6
5 10
2 7

样例输出

3
0
1
1

数据范围与提示

子任务 分数 限制
1 10 \max (n,m)\le 100
2 10 \max (n,m)\le 2000
3 20 \max (n,m)\le 50000
4 20 for each operation, x\le 100
5 20 for each operation, y\le 10
6 20