Fișierul intrare/ieșire	felinare.in, felinare.out	Sursă	ONI 2008 clasa a 5-a
Autor	Marinel Șerban	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Felinare (clasa a 5-a)

Piața centrală a orașului Bacău are formă circulară. De jur împrejurul pieței au fost montate n felinare numerotate de la 0 la n-1. Fiecare felinar poate avea două stări: aprins sau stins. Seara, toate felinarele se aprind simultan. Turistul Vasile T. Popescu începe să se plimbe de jur împrejurul pieței, pornind de la felinarul 0 spre felinarul 1, apoi de la 1 spre 2, ..., de la n-2 spre n-1, de la n-1 spre 0 etc, iar atunci când trece pe lângă un felinar, el execută exact una dintre următoarele operații:

• dacă felinarul precedent (i-1 dacă i > 0 sau n – 1 dacă i = 0) este aprins, atunci schimbă starea felinarului curent (dacă era aprins îl stinge, dacă era stins îl aprinde);
• dacă felinarul precedent este stins, atunci starea felinarului curent rămâne neschimbată.

Cerință

Determinați numărul minim de operații pe care trebuie să le execute turistul nostru până când felinarele sunt aprinse din nou toate.

Date de intrare

Fișierul de intrare felinare.in conține pe prima linie numărul natural n reprezentând numărul de felinare.

Date de ieșire

Fișierul de ieșire felinare.out va conține o singură linie pe care va fi scris un singur număr natural reprezentând numărul minim de operații ce trebuie să fie executate pentru ca toate felinarele să fie din nou aprinse.

Restricții

• 2 ≤ n ≤ 5000
• n este de forma 2^k sau 2^k+1
• Turistul stinge cel puțin un felinar.

Exemplu