状態が変化する操作の度に，新しく黒色で塗られたマスを \(1\) つ選んで記録することにします．

記録されたマスの列が \(p_1,p_2,\cdots,p_k\) であるような操作が可能かどうかを考えてみます． これは操作を逆から見ると判定できます． まず，すべての操作を \(1\) 度ずつ行った状態から始めます． その後，各 \(i=k,\cdots,1\) についてこの順に以下の操作を行います．

• マス \(p_i\) が黒く塗られているかチェックする．白だった場合，失敗と報告する．

• \(L_j \leq p_i \leq R_j\) を含む操作 \(j\) をすべてなかったことにする．

あとは，この判定問題の答えが Yes になるような最長のマスの列を求めればよいです．

ところで，\(p_k\) について考えたあとは，\(p_k\) をまたぐような区間はすべて考えなくて良くなるので，問題が \([1,p_k-1]\) と \([p_k+1,N]\) に分割されます．

よって，区間 DP によってこの問題を解くことができます． \(dp[l][r]=\)区間 \([l,r]\) に完全に含まれる操作だけを考えたときの最適解，として計算すればよいです．

\(dp[l][r]\) を求める際は，この区間内で最後に黒く塗られるマス \(m\) として \(l \leq m \leq r\) をチェックすればよいです． もちろん，\(m\) として選べるのは，\([l,r]\) 内の操作で黒く塗られるマスだけです． 区間 \([l,r]\) 内に含まれる操作の個数 \(cnt[l][r]\) を累積和で計算しておけば，あるマス \(m\) が黒く塗られているかどうかは \(cnt[l][m-1]+cnt[m+1][r]<cnt[l][r]\) で判定できます．

計算量は全体で \(O(N^3)\) になります．

解答例