תיאור הבעיה

מיון בועות (Bubble sort) הוא אחד האלגוריתמים למיון סדרה. נניח שאנו רוצים למיין סדרה $A$ באורך $N$ בסדר עולה. מיון בועות מחליף את המיקומים של $2$ מספרים סמוכים אם יחס הסדר ביניהם הפוך. סריקה אחת מורכבת ממעבר על הסדרה מההתחלה ועד הסוף, והחלפת $2$ המספרים הללו בכל מקום שבו מתקיים $A_i > A_{i+1}$ עבור $i = 1, 2, \dots, N - 1$ בסדר זה. ידוע שחזרה על סריקה זו $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$.

פלט

הדפיסו לפלט הסטנדרטי בשורה $1$ מספר שלם המייצג את המספר המינימלי של החלפות באמצעות מיון בועות על הסדרה $A'$.

קריטריונים לניקוד

• עבור $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

על ידי החלפת האיבר ה-$3$ שהוא $7$ והאיבר האחרון שהוא $5$ בסדרה $A$, הסדרה $A'$ הופכת ל-$3, 1, 5, 9, 7$. מספר ההחלפות באמצעות מיון בועות על $A'$ הוא $2$.

קלט לדוגמה 3

3
1
2
3

פלט לדוגמה 3

1

גם אם הסדרה $A$ ממוינת מלכתחילה, חובה לבצע החלפה בעת יצירת הסדרה $A'$.