F. Tangalar o‘yini 2

A masaladagi o‘yin Durdonaga yoqib qoldi va u o‘yinni kattalashtirdi: endi son o‘qining har xil butun nuqtalarida n ta tanga turibdi.

Bir harakatda u eng chapdagi yoki eng o‘ngdagi tangani oladi va boshqa bo‘sh butun nuqtaga qo‘yadi — lekin shunday qilib, ko‘chirilgan tanga yana chetda qolmasin (ya’ni u qolgan tangalarning eng chapi va eng o‘ngi orasiga tushsin). Barcha tangalar ketma-ket nuqtalarda yonma-yon turganda harakat qilib bo‘lmaydi va o‘yin tugaydi.

O‘yin eng kamida va eng ko‘pi bilan nechta harakatda tugashi mumkin?

Kirish ma’lumotlari

Birinchi qatorda n. Ikkinchi qatorda n ta har xil butun son — tangalar turgan nuqtalar.

Chiqish ma’lumotlari

Bitta qatorda ikki son: harakatlarning eng kam va eng ko‘p soni.

Cheklovlar

• 3 ≤ n ≤ 10⁵
• 1 ≤ nuqtalar ≤ 10⁹, hammasi har xil

1-misol: 4 7 9. Eng kami — 1 harakat: 4 ni 8 ga (7, 8, 9). Eng ko‘pi — 2: 9 ni 5 ga (4, 5, 7), keyin 4 ni 6 ga (5, 6, 7).

2-misol: 3 4 5 6 10. Eng kami — 2: bitta 10 ni 7 ga qo‘yib bo‘lmaydi (u yana chetda qolardi), shuning uchun 3 → 7, so‘ng 10 → 8. Eng ko‘pi — 3.