Given a permutation \(P\), define \(h_i\) as the number of \(j\) such that \(i < j\) and \(\max(P_i,\ldots,P_j)=P_j\).

All the conditions can be written in terms of \(h_i\).

First, \(h\) corresponds to some permutation \(P\) exactly when the following conditions hold.

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

Then, the condition \((l,r,c)\) on an interval can be expressed as \(h_l=\min(h_l,\cdots,h_r)+c-1\).

If we can find an \(h\) satisfying all of these, it is easy to recover \(P\) from it. Therefore, let us consider finding \(h\).

This can be done by repeatedly updating a lower bound \(x_i\) of \(h_i\). More precisely, \(x_i\) is a value such that \(h_i\) is at least \(x_i\) in every solution \(h\).

First, initialize \(x_i=0\). Then, perform the following updates as long as any of them applies.

• If \(x_i>x_{i+1}+1\), update \(x_{i+1}:=x_i-1\).
• If \(x_{L_i} < \min(x_{L_i},\cdots,x_{R_i})+C_i-1\), update \(x_{L_i} := \min(x_{L_i},\cdots,x_{R_i})+C_i-1\).
• If \(x_{L_i}-(C_i-1)>x_j\) (\(L_i \leq j \leq R_i\)), update \(x_j := x_{L_i}-(C_i-1)\).

If some \(x_i\) satisfies \(x_i > N-i\), we know at that point that no \(h\) satisfies the conditions, so the answer is No.

When the updates terminate, the current \(x\) can be adopted as \(h\), so the construction succeeds.

There are at most \(O(N^2)\) updates, and each update can be done in \(O(N^2)\) time, so the problem can be solved in \(O(N^4)\) time overall.

Sample solution (C++)