When given a constraint \(x_i>x_{i+1}>\cdots>x_j\), it is clear that \(i<j\) and \(x_i>x_j\) hold. Therefore, the number of such pairs \((i,j)\) is a lower bound for the inversion number.

This lower bound can actually be achieved. For example, you can construct it as follows:

• Set \(x_1=1\).
• If the \(i\)-th character of \(S\) is <, set \(x_{i+1}=x_i+10^9\).
• If the \(i\)-th character of \(S\) is >, set \(x_{i+1}=x_i-1\).

Therefore, you just need to calculate the value of this lower bound. The time complexity will be \(O(N)\).

Sample Solution