CF1055B.Alice and Hairdresser

Alice's hair is growing by leaps and bounds. Maybe the cause of it is the excess of vitamins, or maybe it is some black magic...

To prevent this, Alice decided to go to the hairdresser. She wants for her hair length to be at most $l$ centimeters after haircut, where $l$ is her favorite number. Suppose, that the Alice's head is a straight line on which $n$ hairlines grow. Let's number them from $1$ to $n$. With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length $l$, given that all hairlines on that segment had length strictly greater than $l$. The hairdresser wants to complete his job as fast as possible, so he will make the least possible number of swings of scissors, since each swing of scissors takes one second.

Alice hasn't decided yet when she would go to the hairdresser, so she asked you to calculate how much time the haircut would take depending on the time she would go to the hairdresser. In particular, you need to process queries of two types:

• $0$ — Alice asks how much time the haircut would take if she would go to the hairdresser now.
• $1$ $p$ $d$ — $p$-th hairline grows by $d$ centimeters.

Note, that in the request $0$ Alice is interested in hypothetical scenario of taking a haircut now, so no hairlines change their length.

爱丽丝的头发正以惊人的速度生长。也许这是维生素摄入过量所致，又或许这是某种黑魔法……

为防止这种情况继续发生，爱丽丝决定去理发店修剪头发。她希望剪完后每根头发的长度至多为 $l$ 厘米，其中 $l$ 是她最钟爱的数字。假设爱丽丝的头部是一条直线，在其上生长着 $n$ 根发丝，我们将其编号为 $1$ 至 $n$。理发师每次挥动一次剪刀，可将任意一段连续区间内所有长度严格大于 $l$ 的发丝统一剪短至长度 $l$（即该区间内所有原本长度 $\leq l$ 的发丝保持不变）。理发师希望尽快完成工作，因此他将采用最少的剪刀挥动次数——因为每次挥动剪刀耗时 1 秒。

目前爱丽丝尚未确定何时前往理发店，因此她请你帮忙计算：在她不同时刻前往理发店的情况下，理发所需的时间分别是多少。具体而言，你需要处理以下两类查询：

• 0 —— 爱丽丝询问：如果她此刻就去理发店，理发需要多长时间？
• 1 $p$ $d$ —— 第 $p$ 根发丝增长了 $d$ 厘米。

注意：在类型为 0 的查询中，爱丽丝关注的是当前时刻立即理发这一假设性场景，因此发丝长度在此查询过程中不会发生变化。

The first line contains three integers $n$, $m$ and $l$ ($1 \le n, m \le 100\,000$, $1 \le l \le 10^9$) — the number of hairlines, the number of requests and the favorite number of Alice.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the initial lengths of all hairlines of Alice.

Each of the following $m$ lines contains a request in the format described in the statement.

The request description starts with an integer $t_i$. If $t_i = 0$, then you need to find the time the haircut would take. Otherwise, $t_i = 1$ and in this moment one hairline grows. The rest of the line than contains two more integers: $p_i$ and $d_i$ ($1 \le p_i \le n$, $1 \le d_i \le 10^9$) — the number of the hairline and the length it grows by.

第一行包含三个整数 $n$、$m$ 和 $l$（$1 \le n, m \le 100\,000$，$1 \le l \le 10^9$）——分别表示发丝的数量、请求的数量以及 Alice 最喜欢的数字。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）——表示 Alice 所有发丝的初始长度。

接下来的 $m$ 行中，每行描述一个请求，格式如题面所述。

每个请求以一个整数 $t_i$ 开头。若 $t_i = 0$，则你需要计算理发所需的时间；否则 $t_i = 1$，此时有一根发丝生长。该行其余部分还包含两个整数：$p_i$ 和 $d_i$（$1 \le p_i \le n$，$1 \le d_i \le 10^9$）——分别表示发丝的编号及其增长的长度。

For each query of type $0$ print the time the haircut would take.

对于每个类型为 $0$ 的查询，输出理发所需的时间。

Consider the first example:

• Initially lengths of hairlines are equal to $1, 2, 3, 4$ and only $4$-th hairline is longer $l=3$, and hairdresser can cut it in $1$ second.
• Then Alice's second hairline grows, the lengths of hairlines are now equal to $1, 5, 3, 4$
• Now haircut takes two seonds: two swings are required: for the $4$-th hairline and for the $2$-nd.
• Then Alice's first hairline grows, the lengths of hairlines are now equal to $4, 5, 3, 4$
• The haircut still takes two seconds: with one swing hairdresser can cut $4$-th hairline and with one more swing cut the segment from $1$-st to $2$-nd hairline.
• Then Alice's third hairline grows, the lengths of hairlines are now equal to $4, 5, 4, 4$
• Now haircut takes only one second: with one swing it is possible to cut the segment from $1$-st hairline to the $4$-th.

考虑第一个例子：

• 初始时，发线长度分别为 $1, 2, 3, 4$，且仅有第 $4$ 根发线长度超过阈值 $l=3$，理发师可在 $1$ 秒内将其剪短。
• 接着爱丽丝的第二根发线生长，此时各发线长度变为 $1, 5, 3, 4$。
• 此时理发需耗时两秒：需两次挥剪，分别作用于第 $4$ 根和第 $2$ 根发线。
• 然后爱丽丝的第一根发线生长，此时各发线长度变为 $4, 5, 3, 4$。
• 理发仍需两秒：一次挥剪可剪短第 $4$ 根发线，另一次挥剪可剪去从第 $1$ 根到第 $2$ 根发线之间的部分。
• 接着爱丽丝的第三根发线生长，此时各发线长度变为 $4, 5, 4, 4$。
• 此时理发仅需一秒：一次挥剪即可剪去从第 $1$ 根发线到第 $4$ 根发线之间的部分。