Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
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 зам байна:
- $t_{2} = 8$-ыг $t_{4} = 7$-аар солино.
- $t_{1} = 2$-ыг $t_{5} = 7$-аар солино.
2-дахь жишээнд, ганц л зам байна -- Лимак $t_{1} = 200$-ыг $t_{4} = 50$-аар солих ёстой.