Fierarul Erik are la dispoziție un lanț (cu două capete) compus din N verigi.
El vrea să facă în așa fel încât tăind câteva verigi din lanțul inițial și recompunând lanțurile rezultate, să poată obține orice lanț cu lungimea din mulțimea {1 , 2 ,…, N}. Lungimea unui lanţ este numărul de verigi din care este format lanţul.
El dorește însă ca numărul de tăieturi de verigi să fie minim.
Recompunerea unui lanț de poate face prin unirea a două lanțuri cu o verigă tăiată sau prin lipire (când nu este necesară o verigă de legătură):
Cerinţă
Fierarul Erik dorește să afle care este numărul minim de tăieturi necesare pentru a obține lanțuri care să îndeplinească cerințele problemei.
Date de intrare
Fișierul de intrare verigi.in conține pe prima linie numărul natural N, reprezentând numărul de verigi din lanțul inițial.
Date de ieşire
Fișierul de ieșire verigi.out conține pe prima linie numărul minim de verigi care trebuie tăiate.
Restricţii
• 1≤N≤13∙108
• Se consideră că tăietura verigii a și tăietura verigii (N-a) sunt echivalente (nu se ia în considerare simetria)
• Considerăm verigile tăiate ca fiind lanțuri de lungime 1.
Exemple
verigi.in
verigi.out
Explicaţii
9
2
O posibilă succesiune cu număr minim de tăieturi este 4, 7. Astfel, cu lanțuri de lungime 3, 1, 2, 1, 2 se pot obține lanțuri de orice lungime cuprinsă între 1 și 9
