Fan imtihonlari vaqtida barcha talabalar harakatga tushib, qo’llariga kitob ola boshlaydi. Odatda imtihon bilet savollari oldindan beriladi, lekin bu biletlarning hammasiga tayyorlanish qiyin albatta. O’qituvchilar ham doimo bir xil, imtihon paytida biletlarni almashtirib tashlashadi, chunki yonma-yon o’tirgan talabalarga bir xil bilet tushib qolishi mumkin. Bugun ham talabalar imtihon topshirishlari kerak. Auditoriyada N ta talaba bitta qator bo’lib o’tirishibdi. O’qituvchi kelib ularga biletlarini tarqatganda i-talabaga a_i-bilet to’g’ri keldi(1ta bilet bir-nechta talabaga berilishi mumkin). Endi bir-xil biletli talabalar birgalikda imtihon biletiga javob yozishni rejalashtirayapti, lekin o’qituvchi bunga yo’l qo’ymasligi tabiiy hol albatta. Auditoriyada faqat o’qituvchi nazaridan qochib yonma-yon o’tirgan talabalar joy almasha olishadi(ya’ni, i-talaba (i+1)-talaba bilan joy almashina oladi). Siz shunday dastur tuzing, eng kam almashtirish orqali bir xil biletli talabalar bir joyda o’tirishsin.

Kiruvchima`luotlar

Birinchi qatorda N natural soni. (1 ≤ N ≤ 10⁵). Keyingi qatorda N ta butun son, i-talabaga tushgan bilet raqami(1 ≤ a_i ≤ 16).

Chiquvchi ma`lumotlar:

Minimum almashtirishlar sonini chiqaring.