\(x_i>x_{i+1}>\cdots>x_j\) という制約が与えられている場合，明らかに \(i<j\) かつ \(x_i>x_j\) が成立しています．よってそのようなペア \((i,j)\) の個数が，転倒数の下界として考えられます．

そしてこの下界は実際に達成できます． 例えば以下のような構成を行えばよいです．

• \(x_1=1\)
• \(S\) の \(i\) 文字目が < のとき，\(x_{i+1}=x_i+10^9\)
• \(S\) の \(i\) 文字目が > のとき，\(x_{i+1}=x_i-1\)

よってこの下界の値を計算すればよいです． 計算量は \(O(N)\) になります．

解答例