我们如下定义一个序列为平衡序列：

• 每一个长度为 $1$ 的序列都是平衡序列。
• 一个长度为 $2k+1$ 的序列 $S = [S_0, S_1, \dots, S_{2k}]$ 是平衡序列，当且仅当满足以下条件：
  • $[S_0, S_1, \dots, S_{k-1}]$ 是平衡序列。
  • $[S_{k+1}, S_{k+2}, \dots, S_{2k}]$ 是平衡序列。
  • $S_k$ 是序列 $S$ 中所有元素的唯一最大值。

给定一个由整数构成的序列 $A$。记 $A[i \dots j]$ 为序列 $A$ 中从下标 $i$ 到下标 $j$（包含两端）的子序列，其长度为 $j-i+1$。例如，若 $A = [3, 5, 7, 2, 9]$，则：

• $A[1 \dots 3] = [5, 7, 2]$
• $A[4 \dots 4] = [9]$

给定 $Q$ 个查询。每个查询为一次操作，将序列中的某个元素修改为指定值。该操作是累积的。

对于初始状态以及每次查询之后，求满足 $0 \le i \le j \le N-1$ 且 $A[i \dots j]$ 是平衡序列的整数对 $(i, j)$ 的总数。

实现细节

你需要实现以下函数：

long long initialize(int N, vector<int> A)

• $N$：序列的长度。
• $A$：长度为 $N$ 的整数数组。

该函数需要返回满足 $0 \le i \le j \le N-1$ 且 $A[i \dots j]$ 为平衡序列的整数对 $(i, j)$ 的总数。

该函数在开始时仅被调用一次。

long long update_sequence(int p, int v)

该函数表示一次查询操作，将 $A[p]$ 的值修改为 $v$。

该函数需要返回修改后满足 $0 \le i \le j \le N-1$ 且 $A[i \dots j]$ 为平衡序列的整数对 $(i, j)$ 的总数。

在调用 initialize 之后，该函数将被调用 $Q$ 次。

你提交的源代码中不得进行任何输入/输出操作。

限制

• $1 \le N \le 10^5$
• $0 \le Q \le 10^5$
• $1 \le A[i] \le 10^9$（对于所有 $0 \le i \le N-1$）
• 对于所有 update_sequence 调用：
  • $0 \le p \le N-1$
  • $1 \le v \le 10^9$

子任务

样例数据

样例 1

考虑 $N = 4$，$Q = 0$，$A = [1, 1, 1, 1]$。

评测程序调用：

initialize(4, [1, 1, 1, 1])

满足 $A[i \dots j]$ 为平衡序列的 $(i, j)$ 为：

$(0,0), (1,1), (2,2), (3,3)$

因此应返回：

$4$

样例 2

考虑 $N = 12$，$Q = 0$，$A = [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6]$。

评测程序调用：

initialize(12, [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6])

函数返回：

$18$

样例 3

考虑 $N = 7$，$Q = 2$，$A = [1, 3, 4, 4, 2, 1, 6]$。

评测程序依次调用：

• initialize(7, [1, 3, 4, 4, 2, 1, 6])
• update_sequence(3, 1)
• update_sequence(3, 2)

函数返回值依次为：

$7, 9, 8$

样例评测程序

样例评测程序的输入格式如下：

• 第 1 行：$N\ Q$
• 第 2 行：$A[0]\ A[1]\ \dots\ A[N-1]$
• 对于所有 $1 \le k \le Q$：
  • 第 $2+k$ 行：$p\ v$（第 $k$ 次 update_sequence 的参数）

样例评测程序的输出格式如下：

• 第 1 行：initialize 的返回值
• 对于所有 $1 \le k \le Q$：
  • 第 $1+k$ 行：第 $k$ 次 update_sequence 的返回值