题目内容

产线侧在整数坐标轴上布置了 $N$ 个温感锚点，编号 $1$ 到 $N$。第 $k$ 个锚点当前读数位置为 $u_k$，全体位置记为整数数组 $u_1,u_2,\ldots,u_N$。

为衡量锚点覆盖的「最远盲区」，对任意长度 $N$ 的整数数组 $v_1,v_2,\ldots,v_N$，定义：

1. 左端 $L=\min(v_1,v_2,\ldots,v_N)$，右端 $R=\max(v_1,v_2,\ldots,v_N)$。
2. 对每个整数 $t\in\{L,L+1,\ldots,R\}$，其到最近锚点的距离为$$d(t)=\min\bigl(|t-v_1|,|t-v_2|,\ldots,|t-v_N|\bigr).$$
3. 盲区半径定义为这些距离的最大值：$$W(v)=\max\bigl(d(L),d(L+1),\ldots,d(R)\bigr).$$

即只在 $[L,R]$ 内的整点 $t$ 上取最近锚点距离，再取最大。

对读数数组 $u$ 进行 $T$ 次修改：每次将 $u_r$ 改为 $z$。每次修改后输出当前的 $W(u)$。

输入描述

第一行两个整数 $N,T$（$2\le N,T\le 100000$），分别为锚点数量与修改次数。

第二行 $N$ 个整数 $u_1,u_2,\ldots,u_N$（$1\le u_k\le 10^9$），初始位置。

接下来 $T$ 行，每行两个整数 $r,z$（$1\le r\le N$，$1\le z\le 10^9$），表示将编号 $r$ 的锚点位置改为 $z$。

输出描述

输出 $T$ 行，每行一个整数，为对应修改后的 $W(u)$。

样例1

输入

4 2
2 5 9 12
2 7
4 20

输出

2
5

说明

初始 distinct 位置 $2,5,9,12$，相邻半距最大为 $\lfloor(9-5)/2\rfloor=2$，故 $W(u)=2$。

第 $1$ 次将 $u_2$ 从 $5$ 改为 $7$，相邻间距最大仍为 $2$。

第 $2$ 次将 $u_4$ 改为 $20$，出现 $\lfloor(20-9)/2\rfloor=5$，答案为 $5$。