Chariots

Time limit2sMemory limit128 MB

Summary
Construct a permutation of size N avoiding both fixed positions on the two main diagonals, or report impossibility for small N.
Level

Medium5 of 10

Topics
Combinatorics, Math, Greedy
Solved
No attempts yet

Problem

A chariot can move any number of cells horizontally or vertically.

You must place N chariots on an N x N board while satisfying both conditions below.

  1. No two chariots may be in the same row or the same column.
  2. No chariot may be placed on either of the two main diagonals of the board: the diagonal from the top-left corner to the bottom-right corner, or the diagonal from the top-right corner to the bottom-left corner.

Write a program that outputs any placement satisfying the conditions.

Input

The first line contains an integer N (3 <= N <= 100,000).

Output

Print N lines. On the i-th line, print the column number where the chariot in row i is placed.

If more than one placement satisfies the conditions, print any one of them. If no placement is possible, print only -1 on the first line.

Examples2

  1. Example 1

    Input
    4
    Expected output
    3
1
4
2

  2. Example 2

    Input
    3
    Expected output
    -1