C. Баавгай ба дээш-доош

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

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

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

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

Амьдрал дээшилж доошилдог, яг л сайхан дарааллууд шиг.Хэрэв дараах 2 нөхцөлийг хангаж байвал дараалал $t_{1}, t_{2}, ..., t_{n}$-ыг сайхан гэж нэрлэнэ.

  • сондгой $i < n$ бүрийн хувьд $t_{i} < t_{i + 1}$ ;
  • тэгш $i < n$ бүрийн хувьд $t_{i} > t_{i + 1}$ .

Жишээлбэл, $(2, 8)$, $(1, 5, 1)$ болон $(2, 5, 1, 100, 99, 120)$ дарааллууд нь сайхан ба $(1, 1)$, $(1, 2, 3)$ болон $(2, 5, 3, 2)$ нь тийм биш юм.

Лимак баавгайд эерэг бүхэл тоонуудын $t_{1}, t_{2}, ..., t_{n}$ дараалал байжээ.Уг дараалал нь сайхан биш бөгөөд одоо харин Лимак нэг солилтоор үүнийг засахыг хүсэж байгаа юм.Тэрээр $i < j$ гэсэн 2 индекс сонгох ба сайхан дараалалтай болохын тулд $t_{i}$ болон $t_{j}$ элементүүдийг солих юм.Ингэж хийх аргын тоог тоолно уу.Хэрэв солихоор сонгосон элементүүдийн индекс нь ялгаатай байвал уг аргуудыг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд дарааллын уртыг илэрхийлэх ганц бүхэл тоо $n$ ($2 ≤ n ≤ 150 000$) өгөгдөнө.

2-дахь мөрөнд анхны дарааллыг илэрхийлэх $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 150 000$) өгөгдөнө.Мөн өгөгдсөн дараалал нь сайхан дараалал биш байх юм.

Гаралт

Сайхан дараалал гаргахын тулд хийх 2 элементийг яг ганц удаа солих аргуудын тоог хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
5
2 8 4 7 7
Гаралт
2
Оролт
4
200 150 100 50
Гаралт
1
Оролт
10
3 2 1 4 1 4 1 4 1 4
Гаралт
8
Оролт
9
1 2 3 4 5 6 7 8 9
Гаралт
0

Тэмдэглэл

Эхний жишээнд, сайхан дарааллыг нэг солилтоор гаргах 2 зам байна:

  1. $t_{2} = 8$-ыг $t_{4} = 7$-аар солино.
  2. $t_{1} = 2$-ыг $t_{5} = 7$-аар солино.

2-дахь жишээнд, ганц л зам байна -- Лимак $t_{1} = 200$-ыг $t_{4} = 50$-аар солих ёстой.

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