Codeforces Round #804 (Div. 2)
00:12:02 |
Educational Codeforces Round 131 (Rated for Div. 2)
5 өдрийн дараа |
Codeforces Round #805 (Div. 3)
7 өдрийн дараа |
Codeforces Round #806 (Div. 4)
9 өдрийн дараа |
D. Пашмак ба Пармидагийн бодлого
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Пармида ухаантай охин бѳгѳѳд энэ жилийн олимпиадад оролцохыг хүсч байгаа. Мэдээж тэр найз хѳвгүүнээ бас ухаантай байхыг хүсдэг (харамсалтай нь тэр тийм биш)! Пармида Пашмакд дараах сорил бодлогыг бэлджээ.
$a$ дараалал нь $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоонуудаас бүрднэ. $f(l, r, x)$ функцийг $l ≤ k ≤ r$ ба $a_{k} = x$ байх $k$ тоонуудын тоо гэж тодорхойлъё. Түүний даалгавар нь $f(1, i, a_{i}) > f(j, n, a_{j})$ байх $i, j$ $(1 ≤ i < j ≤ n)$ хосуудын тоог олох явдал юм.
Пашмакд сорилтоо давахад нь тусална уу.
Оролт
Эхний мѳрѳнд $n$ $(1 ≤ n ≤ 10^{6})$ бүхэл тоо байрлана. Хоёрдугаар мѳрѳнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$ байрлана.
Гаралт
Бодлогын хариу болох ганц тоог хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
7 1 2 1 1 2 2 1
Гаралт
8
Оролт
3 1 1 1
Гаралт
1
Оролт
5 1 2 3 4 5
Гаралт
0