== include(page="template/taskheader" task_id="zaphod") ==
Președintele galaxiei, Zaphod Beeblebrox, dorește să construiască o nouă rută de explorare galactică, pe o axă pornind de la centrul galaxiei spre periferie. Pe această axă vor fi amplasate _N_ avanposturi cu provizii la coordonatele întregi pozitive distincte _x [~1~], x [~2~], ..., x [~N~]_. Centrul galaxiei are coordonata 0. Al _k_ -lea avanpost este conectat cu precedentele prin două autostrăzi: una către avanpostul _k_ - 1 (de lungime _x ~k~ - x ~k-1~_) și o autostradă expres către centrul galaxiei (de lungime x [~k~]). Primul avanpost este conectat numai cu centrul galaxiei. Ministerul Ecologiei și Ecopatiei îi impune două condiții: toate autostrăzile să aibă lungimi diferite, iar alegerea coordonatelor să fie cea mai mică în ordine lexicografică.
Președintele galaxiei, Zaphod Beeblebrox, dorește să construiască o nouă rută de explorare galactică, pe o axă pornind de la centrul galaxiei spre periferie. Pe această axă vor fi amplasate *N* avanposturi cu provizii la coordonatele întregi pozitive distincte *x[~1~], x[~2~], ..., x[~N~]*. Centrul galaxiei are coordonata 0. Al [*k*]-lea avanpost este conectat cu precedentele prin două autostrăzi: una către avanpostul *k* - 1 (de lungime *x[~k~]* - *x[~k-1~]*) și o autostradă expres către centrul galaxiei (de lungime *x[~k~]*). Primul avanpost este conectat numai cu centrul galaxiei. Ministerul Ecologiei și Ecopatiei îi impune două condiții: toate autostrăzile să aibă lungimi diferite, iar alegerea coordonatelor să fie cea mai mică în ordine lexicografică.
Dându-se un număr _N_, să se determine coordonata _x [~N~]_.
Dându-se un număr *N*, să se determine coordonata *x[~N~]*.
h2. Date de intrare
Fișierul de intrare $zaphod.in$ conține un singur număr, _N_.
Fișierul de intrare $zaphod.in$ conține un singur număr, *N*.
h2. Date de ieșire
În fișierul de ieșire $zaphod.out$ se va tipări coordonata _x [~N~]_.
În fișierul de ieșire $zaphod.out$ se va tipări coordonata *x[~N~]*.
h2. Restricții
* _N_ ≤ 10.000.000
* pentru 40% dintre teste, _N_ ≤ 100.000
* 1 ≤ *N* ≤ 10.000.000
* pentru 40% dintre teste, *N* ≤ 100.000
h2. Exemplu
