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

Xem dạng PDF

Gửi bài giải


Điểm: 0,47 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Nguyễn Tấn Sỹ Nguyên
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.