C. Оруулах эрэмбэлэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Петя бол залуу программер. Тэр аль хэдийн C++ хэлний үндсийг сурсан ба алгоритмуудыг сурахаар болсон. Түүний учирсан хамгийн эхний алгоритм нь оруулах эрэмбэлэлт байсан. Петя уг алгоритмыг хэрэгжүүлдэг кодыг аль хэдийн биччихсэн ба өгөгдсөн $n$ хэмжээтэй тэгээс эхлэн индекслэгдсэн $a$ массивыг өсөх дарааллаар эрэмбэлэдэг.

for (int i = 1; i < n; i = i + 1)  
{  
   int j = i;   
   while (j > 0 && a[j] < a[j - 1])  
   {  
      swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]  
      j = j - 1;  
   }  
}

Петя энэ алгоритмыг зөвхөн $0$-c $n - 1$ хүртэлх тооны сэлгэмэл бүхий массивуудыг эрэмбэлэхэд ашиглана. Тэр өөрийн эрэмбэлэх гэж буй сэлгэмэлийг сонгосон боловч эхлээд тэр үүний хоёр элементийг солихоор шийдсэн. Хоёр элементийг сонгохдоо Петя эрэмбэлэлтийн функц болох солих үйлдлийн тоог хамгийн бага байлгахаар сонгохыг хүссэн. Петяд солих үйлдэл хийж чадах мөн энэ шаардлагыг хангах замуудын тоог олоход туслана уу.

Солих функцийн дуудагдах тоог багасгаж байхаар оролтын хоёр элементийг солих боломж үргэлж байх нь тодорхой.

Оролт

Эхний мөрөнд нэг бүхэл тоон утга $n$ ($2 ≤ n ≤ 5000$) байх ба сэлгэмэлийн урт юм. Хоёр дахь мөрөнд $0$ болон $n - 1$ тоонуудыг оролцуулсан энэ хооронд орших ялгаатай $n$ бүхэл тоон утгуудыг агуулсан анхны сэлгэмэл байна.

Гаралт

Хоёр бүхэл тоон утга хэвлэх ба солих функцийн ажиллах хамгийн бага тоо ба ийм боломжийг үүсгэхээр $(i,j)$ хосыг сонгох тоо.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
4 0 3 1 2
Гаралт
3 2
Оролт
5
1 2 3 4 0
Гаралт
3 4

Тэмдэглэл

Эхний жишээн дээр тохирох хосууд нь $(0, 3)$ ба $(0, 4)$.

Хоёр дахь жишээн дээр тохирох хосууд нь $(0, 4)$, $(1, 4)$, $(2, 4)$ ба $(3, 4)$.

Сэтгэгдлүүдийг ачааллаж байна...