順列 \(P\) が与えられたときに，\(h_i\) を，\(i < j\) かつ \(\max(P_i,\ldots,P_j)=P_j\) を満たす \(j\) の個数と定義します．

ここで，すべての条件を \(h_i\) を使って書くことが出来ます．

まず，順列 \(P\) が存在するための条件として，以下の条件が出てきます．

• \(h_N=0\)
• \(0 \leq h_i \leq h_{i+1}+1\) (\(1 \leq i \leq N-1\))

そして，区間の Record 条件 \((l,r,c)\) は，\(h_l=\min(h_l,\cdots,h_r)+c-1\) と表現できます．

これをすべて満たす \(h\) を求めることが出来れば，そこから \(P\) を復元するのは簡単です． よって \(h\) を求めることを考えます．

これは，\(h_i\) の下限 \(x_i\) を更新していけばよいです． より正確に言えば，\(x_i\) は，任意の解 \(h\) における \(h_i\) は \(x_i\) 以上である，という値です．

まず初期値として \(x_i=0\) とします． その後，以下のような更新を行える限り行います．

• \(x_i>x_{i+1}+1\) なら，\(x_{i+1}:=x_i-1\) と更新する．
• \(x_{L_i} < \min(x_{L_i},\cdots,x_{R_i})+C_i-1\) なら，\(x_{L_i} := \min(x_{L_i},\cdots,x_{R_i})+C_i-1\) と更新する．
• \(x_{L_i}-(C_i-1)>x_j\) (\(L_i \leq j \leq R_i\)) なら，\(x_j := x_{L_i}-(C_i-1)\) と更新する．

\(x_i > N-i\) となる \(x_i\) が出てきたら，その時点で条件を満たす \(h\) は存在しないと分かるので答えは No です．

更新が終了した場合，その時点での \(x\) を \(h\) として採用できるので構築に成功します．

更新は高々 \(O(N^2)\) 回で，一回の更新は \(O(N^2)\) で出来るので全体 \(O(N^4)\) でこの問題は解けます．

解答例(C++)