Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
E. Жэфф ба Сэлгэмэл
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Жэффийн найзууд түүнийг төрсөн өдрөөрөө дараалал цуваа авах дуртай хангалттай сайн мэддэг. Тиймдээ ч Жэфф төрсөн өдрөөрөө $p_1,p_2,...,p_n$ дараалал авчээ.
Жэфф дараалал дахь инверсд дургүй. $a_1,a_2,...,a_n$ дараалал дахь инверс гэдэг нь $a_i>a_j$ байх $i,j (1\le i Жэфф $p$ дарааллын зарим элементийг $-1$-р үржүүлж болно. Үүгээрээ тэр энэ дараалал дахь инверсийн тоог хамгийн бага байлгахыг хүсч байгаа. Түүнд тусалж инверсийн тоог хамгийн бага утганд нь хүргэнэ үү. Эхний мөрөнд $n (1\le n\le 2000)$ бүхэл тоо өгөгдөнө. Дараагийн мөрөнд $n$ тооноос тогтох $p_1, p_2, ..., p_n (|p_i|\le 10^5)$ дараалал өгөгдөх ба зайгаар тусгаарлагдсан байна. Нэг мөрөнд бодлогын хариу болох тоог хэвлэнэ үү. (минимум инверсийн тоо)Оролт
Гаралт
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
2 2 1
Гаралт
0
Оролт
9 -2 0 -1 0 -1 2 1 0 -1
Гаралт
6