ARC211-C Forest
まず「どのように操作したとき最大値を得られるか？」を考える。
1回の操作で木の塊を2つ以上消すのは無駄なので、毎回1つずつ消すものとしてよい。両端の木の塊は操作に影響しないため、最初から削っておく。そのうえでの木の塊の個数を$ nとする。このとき、操作は合計で$ n回行われ、木のない区間が$ 2n個指定される。この中には初期状態の木のない区間$ n+1個が必ず含まれる。そのため、残った$ n-1個をできるだけ答えが大きくなるように取る必要があり、すなわち初回の操作で全体の最大値を解放する必要がある。逆に全体の最大値を解放できた場合、残りの操作は最大値を含む部分を片方に指定し続ければよい。
あとは最大値を含むような選び方を数えればよい。自分の場合、木のない区間$ [l_0,r_0],\cdots,[l_n,r_n] をランレングス圧縮で求め、$ [l_i,r_{i+1}] の最大値が（両端の木の塊除く）全体の最大値と一致するなら$ [l_i,r_i] の最大値の個数と$ [l_{i+1},r_{i+1}] の最大値の個数を掛けたものを答えに足していった。
コメント
どのように操作すれば最適になるかを考えるのは典型
解説だと自明な上界が達成可能として考えてたけどこれに至れなかった 反省