Masala #1161

Xotira 64 MB Vaqt 500 ms
14

Navbat

Yaqin kunlarda Robocontest futbolkalari sotuvga chiqa boshladi. Futbolkalar omma orasida shunchalar mashxur bo'lib ketdi-ki, uzun qatorlarda navbatlar paydo bo'ldi. Endi ularni bir savol qiziqirib qo'ydi. Nechta turli juftliklar bir-birini to'g'ridan-to'g'ri ko'ra olishadi?

Bunda 2 kishi bir-birini ko'ra olishi uchun quyidagi holatlardan biri bo'lishi kerak:

    1) ular orasida hech kim bo'lmasligi kerak.

    2) ular orasida ularning hech biridan uzun inson bo'lmasligi kerak.

Bunday juftliklar nechta ekanligi aniqlovchi dastur tuzing.


Kiruvchi ma'lumotlar:

Kirish faylida birinchi qatorda 1 ta natural son \(N(1 \le N \le 500 000)\) navbatdagilar soni.

Keyingi N ta qatorda bittadan natural son mos ravishda navbatdagilarning bo'yi uzunliklari. Bunda ular \(2^{31}\) dan oshmaydi.


Chiquvchi ma'lumotlar:

Chiqish faylida bir-birini ko'rishi mumkin bo'lgan juftliklar sonini chop eting.


Misollar
# input.txt output.txt
1
7
2
4
1
2
2
5
1
10
Izoh:

1-testda har bir yonma-yon turgan inson bir-birini ko'ra olishadi. Bunday juftliklar 6 ta.

Bundan tashqari juftliklar {4, 2}, {4, 2}, {4, 5}, {2, 5}