progresie

Cerință

Să se determine un șir strict crescător, cu lungimea $N$, format din numere naturale nenule, $1 \leq a_1 \lt a_2 \lt a_3 \lt \dots \lt a_N \leq \lfloor 2 \cdot N \cdot \sqrt{N} \rfloor$, cu proprietatea că oricare trei termeni distincți ai șirului nu sunt în progresie aritmetică, adică pentru oricare numere naturale $i$, $j$ și $k$ cu $1 \leq i \lt j \lt k \leq N$, este îndeplinită condiţia: $a_i + a_k \neq 2 \cdot a_j$. Prin $\lfloor x \rfloor$ s-a notat partea întreagă a lui $x$.

De exemplu, pentru $N = 5$, cel mai mare termen al șirului va trebui să fie mai mic sau egal cu $\lfloor2 \cdot 5 \cdot \sqrt{5} \rfloor$, adică $a_N \leq 22$, deci o soluție este: $1, 2, 4, 5, 10$.

Date de intrare

Fişierul de intrare progresie.in conţine pe primul rând numărul natural $N$ cu semnificația de mai sus.

Date de ieșire

În fişierul de ieşire progresie.out se vor scrie pe primul rând, despărțite prin câte un spațiu, cele $N$ elemente ale șirului $a_i$, $1 \leq i \leq N$.

Restricții și precizări

• $3 \leq N \leq 20 \ 000$
• Dacă soluția nu este unică, se va accepta orice soluție corectă.

Exemplul 1

progresie.in

5

progresie.out

1 2 4 5 10

Exemplul 2

progresie.in

7

progresie.out

3 5 6 11 12 14 15