F. Kim kimni ko‘radi?

Bayram tadbiri oldidan N ta o‘quvchi bir qatorga saf tortdi. Chapdan i-o‘quvchining bo‘yi — hᵢ.

Ikki o‘quvchi (i < j) bir-birini ko‘radi, agar ular orasida turgan har bir o‘quvchi ikkalasidan ham baland bo‘lmasa, ya’ni har bir i < k < j uchun h_k ≤ min(hᵢ, hⱼ). Xususan, yonma-yon turgan o‘quvchilar doim bir-birini ko‘radi. Bo‘yi teng o‘quvchi to‘sib qo‘ymaydi.

Sinf rahbari Bobur aka bir-birini ko‘radigan juftliklar nechta ekanini bilmoqchi. Har juftlik bir marta sanaladi.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son N — o‘quvchilar soni.

Ikkinchi qatorda N ta butun son h₁, h₂, …, h_N — bo‘ylar (chapdan o‘ngga).

Chiqish ma’lumotlari

Bitta butun son — bir-birini ko‘radigan juftliklar soni.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 1 ≤ hᵢ ≤ 10⁹
• Javob 32 bitli songa sig‘masligi mumkin: C++ da long long ishlating.

1-misol: yonma-yon juftliklar — 5 ta. Bundan tashqari (2, 4), (2, 5), (2, 6) va (4, 6) juftliklar ham bir-birini ko‘radi — masalan, 2- va 6-o‘quvchi orasidagilar (1, 2, 2) ikkalasidan past. 1- va 3-o‘quvchi esa ko‘rmaydi: orasidagi 2-o‘quvchi (4) ikkalasidan baland. Jami 9.

2-misol: bo‘ylar teng — hamma hammani ko‘radi: 3 juftlik.