该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题为 F 题，与 E. 风传花信，雨濯春尘 题面类似，不同之处已加粗，请留意题号，谨防交错题。

题目背景

几年前的金秋，XG 意外获得了一个长度为 $n$ 的数组 $a$。时至今日，XG 在打完三角洲的某个下午，突然想起了这个数组。

题目描述

他想对这个长度为 $n$ 的数组 $a$ 进行 $q$ 次修改，一次修改为下面两种操作任选其一：

1. 分别选择两个整数 $l, r$ $(1 \leq l \leq r \leq 10^9)$，使得 当前$^{\dagger}$ 所有满足条件 $l \leq a_{i} \leq r$ 的 $a_{i}$ 加 $1$。
2. 分别选择两个整数 $l, r$ $(1 \leq l \leq r \leq 10^9)$，使得 当前$^{\dagger}$ 所有满足条件 $l \leq a_{i} \leq r$ 的 $a_{i}$ 减 $1$。

请你帮他找出 每次修改后数组的最大值。

$^{\dagger}$此处指的是 上一次修改完的 数组 $a$。

输入格式

第一行包含两个整数 $n, q$ $(1\leq n,q \leq 10^5)$，分别表示数组 $a$ 的长度和修改次数。

第二行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq 2 \times 10^5)$，代表数组 $a$。

接下来共有 $q$ 行，每行包含三个整数 $c_j, l_j, r_j$ $(c_j \in \{1, 2\}, 1 \leq l_j \leq r_j \leq 10^9)$，代表第 $j$ 次修改，并且选择了第 $c_j$ 种操作。

输出格式

对于每次修改，输出一行一个整数，表示数组当前最大值。

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

7
8
8
7

4 4
4 4 4 4
1 4 4
1 5 5
1 6 6
1 7 7

5
6
7
8

说明

对于样例 $1$：

第一次修改后数组变为 $\{1,2,4,5,5,6,7\}$，最大值是 $7$;

第二次修改后数组变为 $\{1,2,4,5,5,7,8\}$，最大值是 $8$;

第三次修改后数组变为 $\{1,2,4,5,5,8,8\}$，最大值依然是 $8$;

第四次修改后数组变为 $\{0,1,3,4,4,7,7\}$，最大值是 $7$。