Deskripsi Masalah

Bubble sort adalah salah satu algoritma untuk mengurutkan suatu barisan. Misalkan kita ingin mengurutkan barisan $A$ yang panjangnya $N$ dalam urutan menaik. Bubble sort menukar posisi $2$ bilangan yang bersebelahan jika urutan besar-kecilnya terbalik. Satu kali pemindaian dilakukan dengan menelusuri barisan dari depan ke belakang, yaitu untuk $i = 1, 2, \dots, N - 1$ secara berurutan, jika terdapat posisi di mana $A_i > A_{i+1}$, maka tukar ke-$2$ bilangan tersebut. Diketahui bahwa dengan mengulangi pemindaian ini sebanyak $N - 1$ kali, barisan tersebut dapat diurutkan secara menaik.

Jumlah pertukaran dengan bubble sort pada barisan $A$ adalah banyaknya pertukaran bilangan bulat yang terjadi ketika algoritma di atas diterapkan pada barisan $A$. (Meskipun algoritma dan implementasi yang dikenal sebagai bubble sort mungkin memiliki perbedaan kecil dalam urutan perulangan, rentang, serta kondisi berhenti, diketahui bahwa jumlah pertukaran bilangan bulat saat diterapkan pada barisan yang sama tidak berubah akibat perbedaan-perbedaan tersebut.)

Sebagai contoh, program berikut adalah fungsi dalam bahasa C yang mengurutkan larik bilangan bulat a sepanjang n menggunakan bubble sort.

void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* The following 3 lines correspond to 1 swap of integers */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

Tugas

Diberikan sebuah barisan $A$ sepanjang $N$. Misalkan kita membuat barisan $A'$ dengan menukar $2$ bilangan bulat pada posisi sembarang dalam barisan $A$ tepat $1$ kali. Buatlah program untuk mencari nilai minimum dari jumlah pertukaran dengan bubble sort pada barisan $A'$. (Perhatikan bahwa $2$ bilangan bulat yang ditukar di awal tidak harus bersebelahan.)

Batasan

• $1 \le N \le 100000$: panjang barisan $A$.
• $1 \le A_i \le 1000000000$: besarnya bilangan yang terdapat dalam barisan $A$.

Masukan

Bacalah data berikut dari Masukan Standar:

• Pada baris ke-$1$, tertulis sebuah bilangan bulat $N$. $N$ menyatakan panjang barisan $A$.
• Pada baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya, tertulis sebuah bilangan bulat $A_i$. Ini menyatakan bilangan bulat ke-$i$ dari barisan $A$.

Keluaran

Cetak sebuah bilangan bulat yang menyatakan jumlah pertukaran minimum dengan bubble sort pada barisan $A'$ dalam $1$ baris ke Keluaran Standar.

Kriteria Penilaian

• Untuk $10\%$ dari total nilai, $N \le 1000$, dan $A_i \ne A_j$ berlaku untuk setiap $i, j$ ($1 \le i < j \le N$).
• Untuk $30\%$ dari total nilai, $N \le 5000$, dan $A_i \ne A_j$ berlaku untuk setiap $i, j$ ($1 \le i < j \le N$).
• Untuk $80\%$ dari total nilai, $A_i \ne A_j$ berlaku untuk setiap $i, j$ ($1 \le i < j \le N$).

Contoh

Contoh Masukan 1

5
10
3
6
8
1

Contoh Keluaran 1

0

Jika kita menukar $10$ yang pertama dengan $1$ yang terakhir pada barisan $A$, barisan $A'$ menjadi barisan yang sudah terurut, sehingga jumlah pertukaran pada bubble sort adalah $0$.

Contoh Masukan 2

5
3
1
7
9
5

Contoh Keluaran 2

2

Dengan menukar elemen ke-$3$ yaitu $7$ dengan elemen terakhir yaitu $5$ pada barisan $A$, barisan $A'$ menjadi $3, 1, 5, 9, 7$. Jumlah pertukaran dengan bubble sort pada $A'$ adalah $2$.

Contoh Masukan 3

3
1
2
3

Contoh Keluaran 3

1

Meskipun barisan $A$ sudah terurut sejak awal, pertukaran tetap harus dilakukan saat membuat barisan $A'$.