Alice and Hairdresser

题意翻译

Alice的$n$根头发又在疯长啦，她准备去剪发，同时她心里有一个长度的最佳值$l$，每根长于$l$的头发她的理发师就得花1秒挥剪子。同时，理发师也可以花1秒剪掉一排全部严格长于$l$的头发。 现在给出$m$个操作，有以下方式: - 0 表示Alice询问假设此时剪头最短需多少秒 - 1 p d 第p跟头发(从1开始)将长高dcm $ $ 第一排给出$n,m,l$ 下面一排$n$个数，$a_i$表示第i跟头发长度 下面$m$排给出操作。 $ $ **样例解释** 一开始只有第4根头发长于3，需要1秒 第二根头发长3cm，此时头发长度为1,5,3,4，理发师需要1秒剪第2根，一秒剪第4根 第一根头发长3cm，此时头发长度为4,5,3,4，理发师可以将第一二根一起剪，第4根剪一次 再接下来长度就为4,5,4,4了，一剪子下去完事。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0

输出样例 #1

1
2
2
1

说明

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.