Let’s call the sequence of positive integers N-perfect
, if the following conditions are satisfied:
- the sequence contains all the numbers 1, 2, …, N;
- its length does not exceed 2N;
- all the numbers in the sequence are different;
- the sum of any of its first k members is divisible by k.
For example, the sequence 1, 3, 2, 6, 8 is 3-perfect.
The only line contains integer N (1 ≤ N ≤ 250000).
Output N-perfect sequence in a single line. Its members must not exceed 1013. Separate numbers with spaces. At least one such sequence always exists. If several answers are possible, output any one of them.
Problem Author: Aleksandr Bacherikov