== 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ă.
Dându-se un număr _N_, să se determine coordonata _x [~N~]_.
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 _x [~1~], x [~2~], ..., x [~N~]_ (centrul galaxiei are coordonata 0). Al _i_ -lea avanpost este conectat de precedentele prin două autostrăzi: una către avanpostul _i_ - 1 (de lungime _x ~i~ - x ~i-1~_) și o autostradă expres către centrul galaxiei (de lungime x [~i~]). 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ă.
h2. Date de intrare
Fișierul de intrare $zaphod.in$ conține un singur număr, _N_.
Fișierul de intrare $zaphod.in$ ...
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$ ...
h2. Restricții
* $N ≤ 10.000.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. zaphod.in |_. zaphod.out |
| 6
| 26
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
Coordonatele avanposturilor sunt 1, 3, 7, 12, 18, 26. Autostrăzile către centrul galaxiei au lungimile 1, 3, 7, 12, 18, 26. Autostrăzile între avanposturi consecutive au lungimile 2, 4, 5, 6, 8.
...
== include(page="template/taskfooter" task_id="zaphod") ==
