#P17837. [ONTAK 2021]AKW

[ONTAK 2021]AKW

水族箱

水族箱底部从左到右分为 NN 个区域,相邻区域间有 N−1N-1 块隔板,第 ii 块隔板高度为 hih_i。水族箱总高度为 101010^{10}。可以向各区域倒入任意数量的水;水位超过隔板高度时,水会向相邻区域流动,最终达到稳定状态。

给定 QQ 个要求 (xi,wi,si)(x_i,w_i,s_i)。若 si=1s_i=1,希望区域 xix_i 的水位达到或超过 wiw_i;若 si=0s_i=0,希望该区域的水位严格小于 wiw_i。求可以同时满足的最多要求数。重复要求分别计数。

输入格式

第一行 N,QN,Q。第二行 N−1N-1 个隔板高度。接下来 QQ 行,每行 xi,wi,six_i,w_i,s_i。

输出格式

输出一个整数,表示最多满足的要求数。

数据范围

2≤N,Q≤5000002\le N,Q\le500000,1≤hi,wi≤1091\le h_i,w_i\le10^9,1≤xi≤N1\le x_i\le N,si∈{0,1}s_i\in\{0,1\}。水位恰好等于隔板高度不算越过隔板。

样例

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