VM 12 Bài 18 - Đổi chỗ

View as PDF

Submit solution


Points: 0.47 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Nguyễn Tấn Sỹ Nguyên
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho hoán vị ~A~ của ~N~ số. Một nghịch thế là 1 cặp ~(u, v)~ mà ~u < v~ và ~A(u) > A(v)~. Bạn được thực hiện tối đa 1 phép đổi chỗ 2 số trong dãy ~A~. Tính số nghịch thế nhỏ nhất có thể đạt được.

Input

  • Dòng 1: ~N~ ~(1 \le N \le 1000)~.
  • Dòng 2: ~N~ số nguyên ~A(i)~. ~1 \le A(i) \le N~.

Output

Ghi ra số cặp nghịch thế nhỏ nhất.

Sample Input

5
4 5 2 3 1

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.