#P5823. 【L&K R-03】课表的排列

【L&K R-03】课表的排列

题目背景

小 L 早上来到教室,发现今天的课表非常有趣。

题目描述

今天的课表是:

语文 数学 英语 语文 英语 数学

今天的课表上一共有三个科目:语文、数学、英语。每个科目都有两节课。每科的两节课间隔的课程数分别为 2,3,12,3,1,从小到大排序后为 1,2,31,2,3,是一个公差为 11 的等差数列。

小 L 想知道,对于更多的科目,具有这样有趣性质的课表是否存在。换句话说,如果课表上一共有 nn 个科目,每个科目都有且仅有两节课,小 L 想知道是否存在一个课表,满足这 nn 科的两节课间隔的课程数从小到大排序后是一个公差为 11 的等差数列。

但是,小 L 只会写时间复杂度为 O((2n)!×nlog2n)O((2n)!\times n\log_2 n) 的算法,于是他求助于你,请你判断是否存在这样的课表,如果存在,还要输出一种可能的情况。

输入格式

输入仅一行,一个 奇数 nn,表示课表上的课程数。

输出格式

输出仅一行。

如果不存在这样的课表,输出 -1

如果存在这样的课表,输出 2n2n 个整数,表示课表。令 1,2,,n1,2,\ldots ,n 中的每一个整数对应一个科目,每个整数在课表中均会出现两次,且满足小 L 的性质。由于可能有多种可能的答案,你可以给出任意一种课表,刚到教室的小 K 会写出程序来检验你的课表是否满足小 L 的性质。

3
1 2 3 1 3 2

提示

本题使用 Special Judge。

本题共 2020 个数据点,每个数据点 55 分。

数据编号 x~x n=n=
1101\sim 10 2x+12x+1
111511\sim 15 200x+1200x+1
162016\sim 20 100000x+1100000x+1