A. Ид шидийн цуваа

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

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

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

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

Валера ид шидэд үнэхээр сонирхолтой. Ид шид түүнийг хаа саагүй ид шид хардаг болтол нь татжээ. Тэрээр ямар ч жигтэй болон сонин үзэгдлийг байгалийн бус үзэгдлээр тайлбарладаг. Гэхдээ хэн Валера тоонуудын жирийн цувааг хүртэл ямар нэгэн үзэсгэлэнтэй болон ид шидтэй хэмээн хардаг тухай бодно гэж?

Валера үнэхээр санаандгүй байдлаар дээрээ цувааны тоонууд бичсэн эртний илгэн цаасны хэсэгтэй болжээ. Тэрээр шуудхан уг цуваан дахь тоонууд нь дурын биш гэж бодов. Өргөн хүрээтэй судалгааны үр дүнд Валера шидэт цуваанд байх ёстой гайхалтай шинжийг олжээ: Хэрэв цувааны хамгийн бага болон хамгийн их тоо нь давхцаж байвал уг цувааг ид шидэт гэнэ.

Тэрээр энэ их ач холбогдолтой нээлтээ тантай хуваалцахаар шийдсэн ба хариуд нь таны тусламжийг хүсжээ. Мундаг оюун болон ухааныг үл хамааран, Валера үнэхээр шаргуу тоолж байгаа ба иймд та түүний ажлыг дуусгах ёстой юм. Таны хийх ёстой зүйл бол илгэн цаасан дээр бичигдсэн анхны тоонуудын цувааны ид шидэт дэд дарааллуудын тоог тоолох юм. Дэд дараалал гэдэг нь дараалсан элементүүдийн хоосон биш дараалал юм.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө. 2-дахь мөрөнд анхны цувааны бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$) өгөгдөнө.

Гаралт

Ганц мөрөнд бодлогын хариултыг хэвлэнэ: энэ нь ид шидэт дэд дарааллуудын тоо байна.

C++ дээр 64 битийн тоонуудыг унших болох бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams-ыг ашиглахыг санал болгоё (та мөн %I64d тодорхойлогчийг ашиглаж болно).

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

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

Оролт
4
2 1 1 4
Гаралт
5
Оролт
5
-2 -2 -2 0 1
Гаралт
8

Тэмдэглэл

Жишээнүүдийн тэмдэглэл:

Шидэт дэд дарааллуудыг эхлэл болон төгсгөлийн хос индексүүд [a;b]-аар тэмдэглэв.

Эхний жишээнд: [1;1], [2;2], [3;3], [4;4], [2;3].

2-дахь жишээнд: [1;1], [2;2], [3;3], [4;4], [5;5], [1;2], [2;3], [1;3].

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