Masala #1161

Xotira 64 MB Vaqt 500 ms Qiyinchiligi 45 %

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}

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin