差が \(1\) である隣接2項を「良いペア」、そうでない隣接2項を「悪いペア」とします。

異なる不等号が連続する部分に分けることを考えます。例えば<>><><<<であれば <>と ><>< と <と< に分かれます。

\(a \lt b \gt c\) または \(a \gt b \lt c\) が成り立つとき、\(|a-b|=1\) と \(|b-c|=1\) が同時に満たされることはないため、それぞれの部分について(文字列の)長さを \(l\) とすると、少なくとも \(\left\lfloor\frac{l}{2}\right\rfloor\) 個悪いペアが存在します。それら以外を全て良いペアにすることは可能です。

\(l\) が奇数の部分では下界を達成する悪いペアの選び方は一意に定まりますが、\(l\) が偶数の部分では複数存在します。

悪いペアの選び方を固定して考えます。悪いペアの間に仕切りを入れると、区切られた各区間は連続する数になります。よって、区間同士の大小関係としてありえるものを数え上げればよいです。

これは、\(n\) を区間の数、 \(s\) を悪いペアの不等号を順に並べたものとすると、 \(n,s\) に対する良い順列の個数となり、挿入DPで求めることができます。(参考: EDPC - T問題の解説)

悪いペアの選び方を固定を外して考えます。 \(l\) が偶数の部分の悪いペアの不等号を順に並べると、\(k\)個の < と \(\left\lfloor\frac{l}{2}\right\rfloor\) \(-k\) 個の > ( \(0 \leq k \leq \left\lfloor\frac{l}{2}\right\rfloor\))またはその逆となるので、挿入dpのindexに直前の不等号が < と > のどちらだったかを持てばよいです。

以上より、\(O(n^2)\) でこの問題を解くことができました。 \(n\leq\frac{N}{2}\) より、これは \(N \leq 10000\) では十分高速です。