โจทย์ปัญหา

การเรียงลำดับแบบฟอง (Bubble sort) เป็นหนึ่งในอัลกอริทึมสำหรับการเรียงลำดับข้อมูล สมมติว่าเราต้องการเรียงลำดับลำดับ $A$ ที่มีความยาว $N$ จากน้อยไปมาก การเรียงลำดับแบบฟองจะสลับตำแหน่งของจำนวน $2$ จำนวนที่อยู่ติดกันเมื่อความสัมพันธ์ของขนาดไม่ถูกต้อง การตรวจผ่านหนึ่งรอบคือการไล่ตรวจลำดับตั้งแต่ต้นจนจบ กล่าวคือ สำหรับ $i = 1, 2, \dots, N - 1$ ตามลำดับนี้ หากมีตำแหน่งที่ $A_i > A_{i+1}$ ก็จะสลับจำนวนทั้ง $2$ นั้น เป็นที่ทราบกันดีว่าการทำซ้ำการตรวจผ่านนี้ $N - 1$ รอบ จะสามารถเรียงลำดับข้อมูลจากน้อยไปมากได้

จำนวนครั้งของการสลับด้วยการเรียงลำดับแบบฟองของลำดับ $A$ คือจำนวนครั้งที่มีการสลับจำนวนเต็มเมื่อใช้อัลกอริทึมข้างต้นกับลำดับ $A$ (แม้อัลกอริทึมและการเขียนโปรแกรมที่เรียกว่าการเรียงลำดับแบบฟองอาจมีความแตกต่างเล็กน้อยในด้านลำดับของลูป ขอบเขต และเงื่อนไขการจบการทำงาน แต่เป็นที่ทราบกันว่าจำนวนครั้งของการสลับจำนวนเต็มเมื่อใช้กับลำดับเดียวกันจะไม่เปลี่ยนแปลงไปตามความแตกต่างเหล่านั้น)

ตัวอย่างเช่น โปรแกรมต่อไปนี้เป็นฟังก์ชันที่เขียนด้วยภาษา C เพื่อเรียงลำดับอาร์เรย์ของจำนวนเต็ม a ที่มีความยาว n ด้วยการเรียงลำดับแบบฟอง

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;
      }
    }
  }
}

งานของคุณ

กำหนดลำดับ $A$ ที่มีความยาว $N$ สมมติว่าเราสร้างลำดับ $A'$ โดยการสลับจำนวนเต็ม $2$ ตัวในตำแหน่งใดก็ได้ของลำดับ $A$ เพียง $1$ ครั้งเท่านั้น จงเขียนโปรแกรมเพื่อหาค่าต่ำสุดที่เป็นไปได้ของจำนวนครั้งของการสลับด้วยการเรียงลำดับแบบฟองของลำดับ $A'$ (โปรดสังเกตว่าจำนวนเต็ม $2$ ตัวที่สลับในตอนแรกไม่จำเป็นต้องอยู่ติดกัน)

ขีดจำกัด

• $1 \le N \le 100000$: ความยาวของลำดับ $A$
• $1 \le A_i \le 1000000000$: ขนาดของตัวเลขที่อยู่ในลำดับ $A$

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน:

• ในบรรทัดที่ $1$ มีจำนวนเต็ม $N$ เขียนอยู่ โดย $N$ แทนความยาวของลำดับ $A$
• ในบรรทัดที่ $i$ ($1 \le i \le N$) ของอีก $N$ บรรทัดถัดมา มีจำนวนเต็ม $A_i$ เขียนอยู่ ซึ่งแทนจำนวนเต็มตัวที่ $i$ ของลำดับ $A$

ข้อมูลส่งออก

พิมพ์จำนวนเต็มที่แทนค่าต่ำสุดของจำนวนครั้งของการสลับด้วยการเรียงลำดับแบบฟองของลำดับ $A'$ ใน $1$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน

เกณฑ์การให้คะแนน

• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $10\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 1000$ และสำหรับ $i, j$ ใดๆ ($1 \le i < j \le N$) จะสอดคล้องกับ $A_i \ne A_j$
• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $30\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 5000$ และสำหรับ $i, j$ ใดๆ ($1 \le i < j \le N$) จะสอดคล้องกับ $A_i \ne A_j$
• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $80\%$ ของคะแนนทั้งหมด สำหรับ $i, j$ ใดๆ ($1 \le i < j \le N$) จะสอดคล้องกับ $A_i \ne A_j$

ตัวอย่าง

ตัวอย่างข้อมูลนำเข้า 1

5
10
3
6
8
1

ตัวอย่างข้อมูลส่งออก 1

0

หากเราสลับ $10$ ตัวแรกกับ $1$ ตัวสุดท้ายของลำดับ $A$ ลำดับ $A'$ จะกลายเป็นลำดับที่เรียงแล้ว และจำนวนครั้งของการสลับในการเรียงลำดับแบบฟองจะเป็น $0$

ตัวอย่างข้อมูลนำเข้า 2

5
3
1
7
9
5

ตัวอย่างข้อมูลส่งออก 2

2

เมื่อสลับ $7$ ซึ่งเป็นตัวที่ $3$ กับ $5$ ซึ่งเป็นตัวสุดท้ายของลำดับ $A$ ลำดับ $A'$ จะกลายเป็น $3, 1, 5, 9, 7$ จำนวนครั้งของการสลับด้วยการเรียงลำดับแบบฟองของ $A'$ คือ $2$

ตัวอย่างข้อมูลนำเข้า 3

3
1
2
3

ตัวอย่างข้อมูลส่งออก 3

1

แม้ว่าลำดับ $A$ จะเรียงลำดับอยู่แล้วตั้งแต่ต้น แต่ในการสร้างลำดับ $A'$ ก็ยังจำเป็นต้องทำการสลับ