高山计数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小豪是一个热爱自然的好孩子,他特别喜欢起伏不平的东西,具体的来说他很喜欢山,特是高山
的是小豪家门口就有一排山(没错,正好排成一排)(不是山的地方默认为平原,即海拔0),小豪认为只要一个山的海拔比他两边的山都,那么这个就被称为高山,每天早上小豪起床之后就会去家门口数山。不过因为山神住在小豪隔壁每天山神随机选择一连续的山并且同时改变山的海拔,小豪觉得这十分的神奇,于是他记下了每天山的海拔变化还有每天的高山的数量(如果一个山的海拔变为了负数(也就是变成了山谷),只要这个山的海拔比他两边的山都高,那么小豪还是固执的认为这个是一个高山)。
然后小豪搬家了。。。。
他最珍爱的记录本也遗失了。。。
不过幸运的是,小豪记录下的的海拔变化还在,而且他还记录下来了刚开始的时候每座山的海拔。
聪明的你能帮小豪重新计算出每天的高山数量吗?

Input

多组输入,第一行为一个整数T代表一共有T组数据(T < = 5)
随后的一行为两个整数n,m。分别代表山的个数和天数(1 < = n < = 100000,m < = 100000)
接下来一行为n个整数,分别为A1,A2..An,代表山的初始海拔(0 < = Ai < = 100)
接下来有m行每行两个整数l,r,d。代表从第l个山到第r个山的海拔同时改变了d(1 < = l < = r < = n,-100 < = d < = 100

Output

输出m+1行,第一行输出初始的时候的高山的数量,第i行输出第i-1的变化之后高山的数量

Sample Input

1
5 3
1 2 3 2 1
2 4 -3
2 2 10
1 5 -10

Sample Output

1
3
2
1

Hint

 

Source

QAsQ