Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMSWAP - Đổi chỗ

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à Au > Av. 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 A1, A2, ..., AN.

Output

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

Giới hạn

  • N ≤ 1000
  • Ai ≤ N

Trong 70% số test, N ≤ 100.

Example

Input

5
4 5 2 3 1

Output

3

Được gửi lên bởi:VOJ Team
Ngày:2012-07-04
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:Nguyễn Tấn Sỹ Nguyên

hide comments
2016-07-23 05:54:26 minhsn
trâu cũng AC
2016-07-13 04:31:45


Last edit: 2016-07-13 04:33:43
2015-04-16 04:44:28 Lương Ðức Tuấn Ðạt
trâu cũng AC
2014-06-07 05:24:54 Thanga2pbc
nhe vl
2014-05-23 05:14:40 Nắng
làm rờ rờ cũng AC 1 đấm :v sướng =))
2014-05-16 05:06:34 Chuyên Nga CNN
Tarjan AC này,đề lừa v~ =))
2014-03-20 01:49:35 CTS
bài này mình dùng hoán vị và binary indexed tree nhưng ko thỏa mãn time...có ai giúp mình nêu ý tưởng ko...
2012-11-03 13:25:57 30s bạn làm ðược gì?
ai co tese hiem hk?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.