Есептің шарты

Көпіршікті сұрыптау — тізбекті сұрыптау алгоритмдерінің бірі. Ұзындығы $N$ болатын $A$ тізбегін өсу ретімен сұрыптағымыз келеді дейік. Көпіршікті сұрыптауда көршілес тұрған $2$ санның үлкен-кішілік реті бұзылған болса, олардың орындары ауыстырылады. Тізбекті басынан бастап ретімен қарап шығып, $i = 1, 2, \dots, N - 1$ үшін осы ретпен $A_i > A_{i+1}$ болатын орын кездессе, сол $2$ санның орнын ауыстыру бір өту деп аталады. Осы өтуді $N - 1$ рет қайталау арқылы тізбекті өсу ретімен сұрыптауға болатыны белгілі.

$A$ тізбегін көпіршікті сұрыптау кезіндегі алмастырулар саны деп $A$ тізбегіне жоғарыдағы алгоритмді қолданғанда бүтін сандардың орындары ауыстырылатын санын айтады. (Көпіршікті сұрыптау ретінде белгілі алгоритмдер мен іске асыруларда циклдердің реті, ауқымы және аяқталу шарттары сияқты ұсақ айырмашылықтар болуы мүмкін. Алайда бір тізбекке қолданған кездегі бүтін сандарды алмастыру саны ол айырмашылықтарға байланысты өзгермейтіні белгілі.)

Мысалы, төмендегі программа — ұзындығы n болатын a бүтін сандар массивін көпіршікті сұрыптау арқылы сұрыптайтын C тілінде жазылған функция.

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

Тапсырма

Ұзындығы $N$ болатын $A$ тізбегі беріледі. $A$ тізбегіндегі кез келген орында тұрған $2$ бүтін санның орнын тек $1$ рет қана ауыстыру арқылы $A'$ тізбегін жасаймыз дейік. $A'$ тізбегін көпіршікті сұрыптау кезіндегі алмастырулар санының ең кіші мәнін табатын программа жазыңыз. (Бастапқыда орындары ауыстырылатын $2$ бүтін санның көршілес тұруы міндетті емес екеніне назар аударыңыз.)

Шектеулер

• $1 \le N \le 100000$: $A$ тізбегінің ұзындығы.
• $1 \le A_i \le 1000000000$: $A$ тізбегіндегі сандардың шамасы.

Кіріс деректер

Стандартты енгізуден келесі деректерді оқыңыз:

• $1$-ші жолда бүтін $N$ саны жазылған. $N$ саны $A$ тізбегінің ұзындығын білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бүтін $A_i$ саны жазылған. Бұл $A$ тізбегінің $i$-ші бүтін санын білдіреді.

Шығыс деректер

Стандартты шығаруға $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

Егер $A$ тізбегінің басындағы $10$ мен соңындағы $1$-дің орнын ауыстырсақ, $A'$ тізбегі сұрыпталған тізбекке айналады да, көпіршікті сұрыптаудың алмастырулар саны $0$ болады.

Кіріс мысалы 2

5
3
1
7
9
5

Шығыс мысалы 2

2

$A$ тізбегінің $3$-ші тұрған $7$ саны мен соңғы $5$ санының орнын ауыстыру арқылы $A'$ тізбегі $3, 1, 5, 9, 7$ болады. $A'$ тізбегінің көпіршікті сұрыптау бойынша алмастырулар саны $2$-ге тең.

Кіріс мысалы 3

3
1
2
3

Шығыс мысалы 3

1

$A$ тізбегі басынан-ақ сұрыпталған болса да, $A'$ тізбегін жасаған кезде міндетті түрде орын ауыстыру жасалуы керек.