Пармида ухаантай охин бѳгѳѳд энэ жилийн олимпиадад оролцохыг хүсч байгаа. Мэдээж тэр найз хѳвгүүнээ бас ухаантай байхыг хүсдэг (харамсалтай нь тэр тийм биш)! Пармида Пашмакд дараах сорил бодлогыг бэлджээ.

$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})$ байрлана.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэ.