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
Сэтгэгдлүүдийг ачааллаж байна...