Educational DP Contest T
数列を \(i\) 番目まで見たときに, \(i+1\) 番目に置ける数値 (条件は関係なく) で \(i\) 番目の数値より大きい数の個数が \(j\) 個であるときの組み合わせの数を \(C(i, j)\) とする.
このとき, \(s_i\) が <
のときは,
\(s_i\) が >
のときは,
となる. 和の部分は累積和をあらかじめ計算しておく.
計算量は \(O(N^2)\) である.