{"raw_statement":[{"iden":"statement","content":"*This is the easy version of the problem. The only difference between the two versions is the constraint on $x$. In this version, $x$ is always $1$.*\n\nIt's raining cats and corgis! ... and a whole bunch of other random animals.\n\nAs a zoology-meteorology-geology triple major, you immediately rush to the field to study the phenomenon. The field is an array of $N$ positions, where the $i^(t h)$ position has elevation $h_i$.\n\nAs you observe the unusual precipitation of animals, you notice that the animals fall from the sky and stack on top of each other. Each animal adds $1$ unit of elevation to the position where it lands. Animals continue to stack on top of each other until all valleys in the landscape are filled. Formally, a valley exists if there exist positions $i, j, k$ such that $1 <= i < j < k <= N$ and $h_i > h_j < h_k$ (Visual example provided below).\n\nYou wonder that if you increase the height of the landscape at position $i$ by $x$ units (*where $x$ is always $1$*), how many animals will fill the resulting landscape.\n\nThe first line of input contains 2 space-separated integers $N, Q \" \"(1 <= N, Q <= 10^5) -$ the size of the landscape and the number of queries to process, respectively.\n\nThe second line of input contains $N$ integers $h_i \" \"(0 <= h_i <= 10^5)$ separated by spaces, representing the initial elevation at the $i^(t h)$ position in the landscape array.\n\nEach of the following $Q$ lines contains two integers $p_i \" \"(1 <= p_i <= N)$ and $x_i \" \"bold((x_i = 1))$, representing the position in the landscape array where the elevation will be increased by $x$ units.\n\n*Note*: The changes made in each query should be preserved and taken into account when processing subsequent queries.\n\nPlease output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query.\n\n"},{"iden":"input","content":"The first line of input contains 2 space-separated integers $N, Q \" \"(1 <= N, Q <= 10^5) -$ the size of the landscape and the number of queries to process, respectively.The second line of input contains $N$ integers $h_i \" \"(0 <= h_i <= 10^5)$ separated by spaces, representing the initial elevation at the $i^(t h)$ position in the landscape array.Each of the following $Q$ lines contains two integers $p_i \" \"(1 <= p_i <= N)$ and $x_i \" \"bold((x_i = 1))$, representing the position in the landscape array where the elevation will be increased by $x$ units.*Note*: The changes made in each query should be preserved and taken into account when processing subsequent queries."},{"iden":"output","content":"Please output $Q$ lines, where the $i^(t h)$ line contains the answer to the $i^(t h)$ query."},{"iden":"examples","content":"Input10 42 1 4 4 5 2 3 4 5 33 17 14 15 1Output8\n7\n6\n6\nInput5 40 5 0 5 02 14 13 11 1Output5\n6\n5\n5\nInput6 20 0 0 0 0 02 14 1Output0\n1\n"},{"iden":"note","content":"  "}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"*这是本题的简单版本。两个版本之间的唯一区别在于 $x$ 的约束。在本版本中，$x$ 始终为 $1$。*\\n\\n天上正下着猫和柯基！…… 还有一大堆其他随机动物。\\n\\n作为一名动物学-气象学-地质学三重专业学生，你立即冲到野外研究这一现象。该野外区域是一个包含 $N$ 个位置的数组，其中第 $i^{\\\\text{th}}$ 个位置的海拔为 $h_i$。\\n\\n当你观察这些异常的动物降水时，你注意到动物从天而降并堆叠在一起。每只动物在其落地位置增加 $1$ 单位的海拔。动物会持续堆叠，直到景观中的所有山谷都被填满。形式化地，若存在位置 $i, j, k$ 满足 $1 \\\\lt eq i < j < k \\\\lt eq N$ 且 $h_i > h_j < h_k$，则存在一个山谷（下方提供了视觉示例）。\\n\\n你好奇的是，若将位置 $i$ 的景观高度增加 $x$ 单位（*其中 $x$ 始终为 $1$*），将有多少只动物填满由此产生的景观。\\n\\n输入的第一行包含两个用空格分隔的整数 $N, Q \\\\ (1 \\\\lt eq N, Q \\\\lt eq 10^5)$ —— 分别表示景观的大小和待处理的查询数量。\\n\\n第二行输入包含 $N$ 个用空格分隔的整数 $h_i \\\\ (0 \\\\lt eq h_i \\\\lt eq 10^5)$，表示景观数组中第 $i^{\\\\text{th}}$ 个位置的初始海拔。\\n\\n接下来的 $Q$ 行中，每行包含两个整数 $p_i \\\\ (1 \\\\lt eq p_i \\\\lt eq N)$ 和 $x_i \\\\ \\\\text{bold}((x_i = 1))$，表示将景观数组中第 $p_i$ 个位置的海拔增加 $x$ 单位。\\n\\n*注意*：每个查询所做的更改应被保留，并在处理后续查询时予以考虑。\\n\\n请输出 $Q$ 行，其中第 $i^{\\\\text{th}}$ 行包含第 $i^{\\\\text{th}}$ 个查询的答案。\\n\"},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个用空格分隔的整数 $N, Q \\\\ (1 \\\\lt eq N, Q \\\\lt eq 10^5)$ —— 分别表示景观的大小和待处理的查询数量。第二行输入包含 $N$ 个用空格分隔的整数 $h_i \\\\ (0 \\\\lt eq h_i \\\\lt eq 10^5)$，表示景观数组中第 $i^{\\\\text{th}}$ 个位置的初始海拔。接下来的 $Q$ 行中，每行包含两个整数 $p_i \\\\ (1 \\\\lt eq p_i \\\\lt eq N)$ 和 $x_i \\\\ \\\\text{bold}((x_i = 1))$，表示将景观数组中第 $p_i$ 个位置的海拔增加 $x$ 单位。*注意*：每个查询所做的更改应被保留，并在处理后续查询时予以考虑。\"},{\"iden\":\"output\",\"content\":\"请输出 $Q$ 行，其中第 $i^{\\\\text{th}}$ 行包含第 $i^{\\\\text{th}}$ 个查询的答案。\"},{\"iden\":\"examples\",\"content\":\"输入\\n10 4\\n2 1 4 4 5 2 3 4 5 3\\n3 1\\n7 1\\n4 1\\n5 1\\n输出\\n8\\n7\\n6\\n6\\n\\n输入\\n5 4\\n0 5 0 5 0\\n2 1\\n4 1\\n3 1\\n1 1\\n输出\\n5\\n6\\n5\\n5\\n\\n输入\\n6 2\\n0 0 0 0 0 0\\n2 1\\n4 1\\n输出\\n0\\n1\\n\"},{\"iden\":\"note\",\"content\":\"  \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ h = [h_1, h_2, \\dots, h_N] $ be the array of initial elevations.\n- A **valley** is a triple of indices $ (i, j, k) $ such that $ 1 \\leq i < j < k \\leq N $ and $ h_i > h_j < h_k $.\n- Each animal increases the elevation of a position by exactly 1 unit.\n- Animals stack until **all valleys are filled**, i.e., no such triple $ (i, j, k) $ exists with $ h_i > h_j < h_k $.\n- After each query, the elevation at position $ p_i $ is increased by $ x_i = 1 $, and the change persists.\n\n**Given:**\n\n- $ N, Q \\in \\mathbb{Z}^+ $, $ 1 \\leq N, Q \\leq 10^5 $\n- Initial array $ h \\in \\mathbb{Z}_{\\geq 0}^N $\n- For each query $ q \\in \\{1, \\dots, Q\\} $: update $ h_{p_q} \\leftarrow h_{p_q} + 1 $\n\n**Objective:**\n\nFor each query $ q $, compute the **minimum number of animals** (i.e., total elevation increases) required to eliminate **all valleys** in the current landscape $ h $, starting from the state after the previous update (or initial state for $ q=1 $).\n\n**Note:** The number of animals needed is the **minimum total elevation increase** across all positions such that the resulting array $ h' $ satisfies:\n\n$$\n\\not\\exists \\, i, j, k \\text{ with } 1 \\leq i < j < k \\leq N \\text{ such that } h'_i > h'_j < h'_k\n$$\n\nThis is equivalent to making the array **valley-free**, which occurs if and only if the array is **bitonic**: i.e., non-decreasing up to some peak, then non-increasing, or more generally, has no local minima strictly lower than both neighbors.\n\nBut note: the minimal way to eliminate all valleys is to raise every local minimum to the height of the **minimum of its two neighboring peaks**.\n\nThus, the minimal number of animals required is the **sum over all local minima** $ j $ of:\n\n$$\n\\max\\left(0, \\min(h_{j-1}, h_{j+1}) - h_j\\right)\n$$\n\n**Formal Output per Query:**\n\nAfter updating $ h_{p_q} \\leftarrow h_{p_q} + 1 $, compute:\n\n$$\n\\sum_{j=2}^{N-1} \\max\\left(0, \\min(h_{j-1}, h_{j+1}) - h_j\\right)\n$$\n\n**Constraints:**\n\n- Updates are persistent.\n- $ x_i = 1 $ for all queries.\n- Only local minima (interior points satisfying $ h_{j-1} > h_j < h_{j+1} $) contribute to the sum.\n\n---\n\n**Final Formal Statement:**\n\nLet $ h^{(0)} = [h_1, h_2, \\dots, h_N] $ be the initial elevation array.\n\nFor $ q = 1 $ to $ Q $:\n\n1. $ h^{(q)}_{p_q} \\leftarrow h^{(q-1)}_{p_q} + 1 $\n2. $ h^{(q)}_i = h^{(q-1)}_i $ for $ i \\ne p_q $\n3. Compute:\n   $$\n   A_q = \\sum_{j=2}^{N-1} \\max\\left(0, \\min(h^{(q)}_{j-1}, h^{(q)}_{j+1}) - h^{(q)}_j\\right)\n   $$\n4. Output $ A_q $\n\n**Note:** The sum is over all interior indices $ j \\in \\{2, 3, \\dots, N-1\\} $, and only contributes when $ h_j $ is strictly less than both neighbors.","simple_statement":null,"has_page_source":false}