Anti-arithmetic permutations

Time Limit:1000ms Memory Limit:64000KiB
Accepted:0 Submitted:5
Anti-arithmetic permutations

POI III Stage III Problem 4

Anti-arithmetic permutations

We call a permutation p0, p1, ... , pn-1 of integers 0, 1, ... , n-1 anti-arithmetic, when there are no three-term arithmetic series in this permutation, i.e. there are no such three indices i < j < k, that integers pi, pj, pk make an arithmetic series. For example the series of integers 3, 1, 0, 4, 2 is an anti-arithmetic permutation of integers 0, 1, 2, 3, 4. The series 0, 5, 4, 3, 1, 2 is not an anti-arithmetic permutation, because its first, fifth and sixth term: 0, 1, 2 form an arithmetic series (as well as its second, forth and fifth term: 5, 3, 1 and second third and forth term: 5, 4, 3 form arithmetic series).

Task

Write a program that:

  • reads one positive integer n from the text file PER.IN,
  • computes any anti-arithmetic permutation of numbers 0, 1, ... , n-1 and writes it into the text file PER.OUT.

Input

There is one positive integer n, 3 <= n <= 1000000, written in the text file PER.IN. 

Output

The output file PER.OUT should be composed of n lines. These lines should contain different integers from the set {0, 1, ... , n-1}, one in each line. The numbers in the consecutive lines should form an anti-arithmetic permutation of numbers 0, 1, ..., n-1.

Example

If there is number 5 written in the input file PER.IN, then one of the correct solutions is the following file PER.OUT :
3
1
0
4
2

SubmitStatistics

SOJ is designed and developed by Wilbur Ding and Liang Sun. ©All Rights Reserved 2009-2012.