题面 下发文件

题目描述

给你一个长度为 $n$ 的序列 $A$ 。

$\forall 1\le i<j\le n$ ，我们称 $(i,j)$ 是合法的，当且仅当：

1. $A_i=A_j$

2. $\forall i<k<j,A_k<A_i$

定义 $A$ 的权值是这样的合法数对 $(i,j)$ 的个数。

你需要在所有修改前输出 $A$ 的权值。

接下来给定 $q$ ，我们会进行 $q$ 次对 $A$ 的修改。

每次修改给定 $x,z$ ，令 $A_x:=z$ ，你需要在每次修改后输出 $A$ 的权值。

输入格式

输入第一行给定一个整数 $n$ 。

第二行包含 $n$ 个整数，第 $i$ 个整数代表 $A_i$ 。

第三行给定一个整数 $q$ 。

接下来 $q$ 行，每行给定两个整数 $x,z$ ，代表一次修改的信息。

输出格式

输出 $q+1$ 行，每行包含一个整数，其中第一行代表所有修改前的答案；$\forall 1\le i\le q$ ，第 $i+1$ 行代表第 $i$ 次修改后的答案。

样例 1

样例输入

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

样例输出

4
3
3
2
2
2
2
2
2
3
3

样例 2~5

见下发文件。

数据范围

对于所有数据，$1\le n\le10^5,1\le q\le 3*10^5$ 。

$\forall 1\le i\le n,1\le A_i\le n$ 。

每次修改保证 $1\le x,z\le n$ 。

特殊性质 A：$\forall 1\le i\le n,A_i\le 5$ 。每次修改 $z\le 5$ 。