Educational Codeforces Round 7-D. Optimal Number Permutation

原题链接

D. Optimal Number Permutation

time limit per test

memory limit per test

input

output

You have array a that contains all integers from 1 to n twice. You can arbitrary permute any numbers in a.

Let number i be in positions xi, yi (xi < yi) in the permuted array a. Let's define the value di = yi - xi — the distance between the positions of the number i. Permute the numbers in array a to minimize the value of the sum 

.

Input

The only line contains integer n (1 ≤ n ≤ 5·105).

Output

Print 2n integers — the permuted array a that minimizes the value of the sum s.

Examples

input

2

output

1 1 2 2

input

1

output

1 1

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define maxn 1000005
#define MOD 1000000007
using namespace std;
typedef long long ll;

int num[maxn];
int main(){
	int n;
	scanf("%d", &n);
	int l = 1, r = n;
	for(int i = 1; i <= n; i += 2){
		num[l] = i;
		num[r] = i;
		l++;
		r--;
	}
	num[n+1] = n;
	l = n + 2;
	r = 2 * n;
	for(int i = 2; i <= n; i += 2){
		num[l] = i;
		num[r] = i;
		l++;
		r--; 
	}
	printf("%d", num[1]);
	for(int i = 2; i <= 2 * n; i++)
	  printf(" %d", num[i]);
	return 0; 
}