Умова задачі

Сортування бульбашкою — один з алгоритмів сортування послідовності. Припустімо, ми хочемо відсортувати послідовність $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'$, рівно $1$ раз помінявши місцями $2$ цілі числа, що знаходяться на довільних позиціях у послідовності $A$. Напишіть програму для знаходження мінімальної можливої кількості обмінів під час сортування бульбашкою послідовності $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'$ обов'язково потрібно виконати обмін.