AL03-5. Kesmalarni birlashtirish

Son o‘qida n ta kesma berilgan. Kesishadigan yoki bir-biriga tegib turgan kesmalarni birlashtiring ([1; 4] va [4; 6] → [1; 6]).

Kesmalarni chap uchi bo‘yicha saralang va chapdan o‘ngga yuring: navbatdagi kesma oxirgi birlashmaga tegsa — uni kengaytiring, aks holda yangisini boshlang.

Kirish ma’lumotlari

Birinchi qatorda n. Keyingi n qatorda kesma uchlari l r.

Chiqish ma’lumotlari

Birinchi qatorda birlashmalar soni, so‘ng har biri chapdan o‘ngga.

Cheklovlar

1 ≤ n ≤ 10⁵, 0 ≤ l ≤ r ≤ 2·10⁹