Đổi chỗ ( VMSWAP )

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho dãy A là một hoán vị gồm N số. Một nghịch thế là một cặp số u, v sao cho u < v và A u > A v . Bạn được thực hiện thao tác đổi chỗ hai số bất kì trong dãy A không quá một lần. Hãy tính số nghịch thế nhỏ nhất có thể đạt được trong dãy A.

Input

  • Dòng 1 chứa số nguyên dương N .
  • Dòng 2 chứa N số nguyên dương A 1 , A 2 , ..., A N .

Output

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

Giới hạn

  • N ≤ 1000
  • A i ≤ N

Trong 70% số test, N ≤ 100.

Example

Input

5
4 5 2 3 1

Output

3


  • Người up: voj
  • Điểm: 0.44
  • Ngôn ngữ cho phép:
  • Nguồn bài: Nguyễn Tấn Sỹ Nguyên