Условие задачи

Сортировка пузырьком — один из алгоритмов сортировки последовательности. Предположим, мы хотим отсортировать последовательность $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'$ обязательно нужно выполнить обмен.