Gatavojoties Lielajiem Siera Svētkiem, pavāri ir sagatavojuši vienu no neiztrūkstošajām svētku sastāvdaļām - siera plati, kas ir liela paplāte ar N siera šķirnēm. Katras šķirnes siers ir sagriezts šķēlēs.
Īsi pirms svētku sākuma svētku virsvadītājs ir izdomājis, ka siera plate izskatītos glītāk, ja visām šķirnēm, kas svētku sākumā atrodas uz siera plates, šķēļu skaits būtu vienāds. Siera plates sakārtošana ir uzticēta jaunākajam pavāram. Tā kā visas siera šķirnes ir īpašas, tad vienīgā pieļaujamā darbība ir dažas siera šķēles apēst. Tiek pieļauta iespēja, ka kādas šķirnes siers tiek apēsts pilnībā, tādējādi samazinot kopējo uz siera plates esošo šķirņu skaitu.
Diemžēl, siers nav jaunākā pavāra mīļākais ēdiens. Tāpēc viņš labprāt apēstu pēc iespējas mazāku siera šķēļu skaitu.
Uzrakstiet programmu, kas dotam sākotnējam siera šķēļu skaitam uz siera plates noteiktu, kāds mazākais šķēļu skaits jāapēd, lai visām uz paplātes palikušajām šķirnēm šķēļu skaits būtu vienāds!
Teksta faila siers.dat pirmajā rindā dots naturāls skaitlis N (1 ≤ N ≤ 1 000 000) - sākotnēji uz siera plates izvietoto siera šķirņu skaits. Katrā no nākošajām N faila rindām dots pa vienam naturālam skaitlim. Katram i (1 ≤ i ≤ N) faila (i+1)-ajā rindā dots naturāls skaitlis si (1 ≤ si ≤ 1 000 000) - i-tās šķirnes siera sākotnējais šķēļu skaits uz siera plates.
Teksta faila siers.rez vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - mazākais apēdamo siera šķēlu skaits.
| siers.dat | siers.rez | Piezīme |
3 113 115 114 |
3 |
Jānoēd divas otrās šķirnes un viena trešās šķirnes siera šķēle. Paliks 113 katras šķirnes šķēles. |
| siers.dat | siers.rez | Piezīme |
4 739 1 740 739 |
2 |
Jānoēd viena otrās šķirnes un viena trešās šķirnes siera šķēle. Uz plates paliks trīs šķirņu siers, kuriem šķēļu skaits būs vienāds - 739. |
| siers.dat | siers.rez | Piezīme |
2 1000000 1000000 |
0 |
Skaits jau ir vienāds nekas nav jāēd. |