题解 | #合唱队#

using System.Linq;
public class Program {
    public static void Main() {
        var n = int.Parse(System.Console.ReadLine());
        var t = System.Console.ReadLine().Split(' ')
            .Select(s => int.Parse(s)).ToArray();
        var lp = new int[t.Length];  // Left part.
        var rp = new int[t.Length];  // Right part.
        for (var i=0; i<t.Length; ++i) {
            lp[i] = i;
            for (var j=i-1; j>=0; --j) {
                if (t[j] < t[i]) {
                    var v = lp[j] + i-j-1;
                    if (v < lp[i]) lp[i] = v;
                }
            }
        }
        for (var i=t.Length-1; i>=0; --i) {
            rp[i] = t.Length-1 - i;
            for (var j=i+1; j<t.Length; ++j) {
                if (t[j] < t[i]) {
                    var v = rp[j] + j-i-1;
                    if (v < rp[i]) rp[i] = v;
                }
            }
        }
        var min = int.MaxValue;
        for (var i=0; i<lp.Length; ++i) {
            var v = lp[i] + rp[i];
            if (v < min) min = v;
        }
        System.Console.WriteLine(min);
    }
}