نص المسألة

الترتيب الفقاعي (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'$.