Lunar rover finally reached planet X. After landing, he met an obstacle, that contains permutation $p$ of length $n$. Scientists found out, that to overcome an obstacle, the robot should make $p$ an identity permutation (make $p_i = i$ for all $i$).

Unfortunately, scientists can't control the robot. Thus the only way to make $p$ an identity permutation is applying the following operation to $p$ multiple times:

Select two indices $i$ and $j$ ($i \neq j$), such that $p_j = i$ and swap the values of $p_i$ and $p_j$. It takes robot $(j - i)^2$ seconds to do this operation.

Positions $i$ and $j$ are selected by the robot (scientists can't control it). He will apply this operation while $p$ isn't an identity permutation. We can show that the robot will make no more than $n$ operations regardless of the choice of $i$ and $j$ on each operation.

Scientists asked you to find out the maximum possible time it will take the robot to finish making $p$ an identity permutation (i. e. worst-case scenario), so they can decide whether they should construct a new lunar rover or just rest and wait. They won't believe you without proof, so you should build an example of $p$ and robot's operations that maximizes the answer.

For a better understanding of the statement, read the sample description.


-----Input-----

The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each of next $t$ lines contains the single integer $n$ ($2 \leq n \leq 10^5$) – the length of $p$.

Note, that $p$ is not given to you. You should find the maximum possible time over all permutations of length $n$.

It is guaranteed, that the total sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case in the first line, print how many seconds will the robot spend in the worst case.

In the next line, print the initial value of $p$ that you used to construct an answer.

In the next line, print the number of operations $m \leq n$ that the robot makes in your example.

In the each of next $m$ lines print two integers $i$ and $j$ — indices of positions that the robot will swap on this operation. Note that $p_j = i$ must holds (at the time of operation).


-----Examples-----

Input
3
2
3
3
Output
1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3


-----Note-----

For $n = 2$, $p$ can be either $[1, 2]$ or $[2, 1]$. In the first case $p$ is already identity, otherwise robot will make it an identity permutation in $1$ second regardless of choise $i$ and $j$ on the first operation.

For $n = 3$, $p$ can be equals $[2, 3, 1]$.

If robot will select $i = 3, j = 2$ on the first operation, $p$ will become $[2, 1, 3]$ in one second. Now robot can select only $i = 1, j = 2$ or $i = 2, j = 1$. In both cases, $p$ will become identity in one more second ($2$ seconds in total).

If robot will select $i = 1, j = 3$ on the first operation, $p$ will become $[1, 3, 2]$ in four seconds. Regardless of choise of $i$ and $j$ on the second operation, $p$ will become identity in five seconds.

We can show, that for permutation of length $3$ robot will always finish all operation in no more than $5$ seconds.

Source: codeforces | Difficulty: VERY_HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	N = int(input())
	res = [i for i in range(1, N + 1)]
	qs = []
	c = 0
	for i in range(N // 2, N):
		qs.append((i + 1, 1))
		(res[0], res[i]) = (res[i], res[0])
		c += i ** 2
	for i in range(1, N // 2):
		qs.append((i + 1, N))
		(res[-1], res[i]) = (res[i], res[-1])
		c += (N - i - 1) ** 2
	print(c)
	print(*res)
	qs.reverse()
	print(len(qs))
	for q in qs:
		print(*q)


import sys
readline = sys.stdin.readline

def parorder(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[p] = -1
	stack = [p]
	order = []
	visited = set([p])
	ast = stack.append
	apo = order.append
	while stack:
		vn = stack.pop()
		apo(vn)
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			ast(vf)
	return (par, order)

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res
T = int(readline())
Ans = []
INF = 2 * 10 ** 9 + 7
for qu in range(T):
	N = int(readline())
	Edge = [[] for _ in range(N)]
	m = N - 1
	Edge[0].append(m)
	Edge[m].append(0)
	ans = m * m
	for i in range(1, N - 1):
		if i - 0 > m - i:
			Edge[i].append(0)
			Edge[0].append(i)
			ans += i * i
		else:
			Edge[i].append(m)
			Edge[m].append(i)
			ans += (m - i) ** 2
	Ans.append(str(ans))
	(P, L) = parorder(Edge, 0)
	pe = list(range(1, N + 1))
	res = []
	for l in L[:0:-1]:
		p = P[l]
		res.append((l + 1, p + 1))
	for (a, b) in res[::-1]:
		a -= 1
		b -= 1
		(pe[a], pe[b]) = (pe[b], pe[a])
	Ans.append(' '.join(map(str, pe)))
	Ans.append(str(N - 1))
	Ans.append('\n'.join(['{} {}'.format(*a) for a in res]))
print('\n'.join(Ans))


def ints():
	return list(map(int, input().split()))

def go():
	(n,) = ints()
	if n <= 3:
		print(sum((i ** 2 for i in range(n))))
		print(' '.join(map(str, range(2, n + 1))), 1)
		print(n - 1)
		for i in range(1, n):
			print(i, n)
	else:
		print(sum((max(i - 1, n - i) ** 2 for i in range(1, n))))
		m = n // 2 + 1
		A = list(range(2, m))
		B = list(range(m, n))
		cycle = [1] + B + [n] + A
		p = [None] * (n + 1)
		for i in range(n):
			u = cycle[i]
			v = cycle[(i + 1) % n]
			p[u] = v
		print(*p[1:])
		print(n - 1)
		for b in B:
			print(b, 1)
		for a in A:
			print(a, n)
		print(1, n)
(num_cases,) = ints()
for case_num in range(num_cases):
	go()


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	AA = []
	for i in range((n + 2) // 2, n):
		AA.append((1, i))
	for i in range((n + 2) // 2 - 1, 0, -1):
		AA.append((i, n))
	L = list(range(1, n + 1))
	sc = 0
	for (x, y) in AA[::-1]:
		(L[x - 1], L[y - 1]) = (L[y - 1], L[x - 1])
		sc += (x - y) ** 2
	print(sc)
	print(*L)
	print(len(AA))
	for (x, y) in AA:
		if L[x - 1] == y:
			print(y, x)
		else:
			print(x, y)
		(L[x - 1], L[y - 1]) = (L[y - 1], L[x - 1])


def main():
	n = int(*input().split())
	L = [x for x in range(n + 1)]
	ans = []

	def swp(x, y):
		(L[x], L[y]) = (L[y], L[x])
	swp(1, n)
	ans.append((1, n))
	for i in range(2, (n + 1) // 2 + 1):
		swp(i, n)
		ans.append((i, n))
		if not n - i + 1 == i:
			swp(n - i + 1, 1)
			ans.append((n - i + 1, 1))
	val = sum(((i - j) * (i - j) for (i, j) in ans))
	print(val)
	for x in range(1, n + 1):
		print(L[x], end=' ')
	print('\n%d' % (n - 1,))
	for x in range(n - 2, -1, -1):
		print(ans[x][0], ans[x][1])
T = int(*input().split())
for ii in range(T):
	main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	time = 0
	integer = [i for i in range(1, n + 1)]
	l = []
	for i in range(n // 2, n):
		time += i ** 2
		(integer[0], integer[i]) = (integer[i], integer[0])
		l.append((i + 1, 1))
	for i in range(1, n // 2):
		time += (n - 1 - i) ** 2
		(integer[-1], integer[i]) = (integer[i], integer[-1])
		l.append((i + 1, n))
	l.reverse()
	print(time)
	print(*integer)
	print(len(l))
	for i in l:
		print(i[0], i[1])


for tests in range(int(input())):
	n = int(input())
	AA = [(1, i) for i in range((n + 2) // 2, n)] + [(i, n) for i in range((n + 2) // 2 - 1, 0, -1)]
	L = list(range(1, n + 1))
	sc = 0
	for (x, y) in AA[::-1]:
		(L[x - 1], L[y - 1]) = (L[y - 1], L[x - 1])
		sc += (x - y) ** 2
	print(sc)
	print(*L)
	print(len(AA))
	for (x, y) in AA:
		print(y, x) if L[x - 1] == y else print(x, y)
		(L[x - 1], L[y - 1]) = (L[y - 1], L[x - 1])


t = int(input())
for lkajshglksdjfbne in range(0, t):
	n = int(input())
	x = [0] * (n + 1)
	x[1] = 1 + n // 2
	x[n] = x[1] - 1
	p = 2
	for i in range(1, n + 1):
		if i == x[1] or i == x[n]:
			continue
		x[p] = i
		p += 1
	raw = x.copy()
	he = 0
	buzhou = []
	while x[1] != n:
		buzhou.append([x[1], 1])
		he += (x[1] - 1) ** 2
		p1 = 1
		p2 = x[1]
		(x[p1], x[p2]) = (x[p2], x[p1])
	while x[n] != n:
		buzhou.append([x[n], n])
		he += (x[n] - n) ** 2
		p1 = x[n]
		p2 = n
		(x[p1], x[p2]) = (x[p2], x[p1])
	print(he)
	for i in range(1, n + 1):
		if i > 1:
			print(' ', end='')
		print(raw[i], end='')
	print()
	print(n - 1)
	for i in buzhou:
		print(i[0], i[1])


def solve():
	n = int(input())
	q = list(range(1, n + 1))
	q = list(range(1, n + 1))
	(q[0], q[n - 1]) = (q[n - 1], q[0])
	res = (n - 1) ** 2
	for i in range(1, n // 2):
		(q[0], q[n - i - 1]) = (q[n - i - 1], q[0])
		(q[i], q[n - 1]) = (q[n - 1], q[i])
		res += 2 * (n - (i + 1)) ** 2
	if n % 2:
		res += (n - n // 2 - 1) ** 2
		(q[0], q[n // 2]) = (q[n // 2], q[0])
	print(res)
	print(*q)
	print(n - 1)
	if n % 2:
		print(n // 2 + 1, 1)
	for i in range(n // 2 - 1, 0, -1):
		print(i + 1, n)
		print(n - i, 1)
	print(n, 1)
for _ in range(int(input())):
	solve()


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	n = int(input())
	pp = list(range(1, n + 1))
	c = 0
	res = []
	(pp[0], pp[n - 1]) = (pp[n - 1], pp[0])
	res.append((1, n))
	c += (n - 1) ** 2
	for i in range(1, n // 2):
		(pp[0], pp[-i - 1]) = (pp[-i - 1], pp[0])
		res.append((n - i, 1))
		(pp[n - 1], pp[i]) = (pp[i], pp[n - 1])
		res.append((i + 1, n))
		c += (n - i - 1) ** 2 * 2
	if n % 2 == 1:
		(pp[0], pp[n // 2]) = (pp[n // 2], pp[0])
		res.append((n // 2 + 1, 1))
		c += (n // 2) ** 2
	print(c)
	print(' '.join(map(str, pp)))
	print(len(res))
	for (i, j) in res[::-1]:
		print(i, j)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def solve():
	n = int(input())
	A = list(range(1, n + 1))
	ops = []
	ans = 0

	def process(i, j):
		nonlocal ans
		(A[i], A[j]) = (A[j], A[i])
		ops.append((i + 1, j + 1))
		ans += (i - j) ** 2
	process(0, n - 1)
	rem = n - 2
	d = 2
	while rem:
		process(n - d, 0)
		rem -= 1
		if rem == 0:
			break
		process(d - 1, n - 1)
		rem -= 1
		d += 1
	print(ans)
	print(*A)
	print(len(ops))
	for (i, j) in reversed(ops):
		print(i, j)
import sys, os, io
input = lambda : sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode('ascii'))
for _ in range(int(input())):
	solve()
os.write(1, stdout.getvalue())


for _ in range(int(input())):
	n = int(input())
	p = [i for i in range(n + 1)]
	ops = []
	for i in range(1, n // 2 + 1):
		ops.append((i, n))
	for i in range(n - 1, n // 2, -1):
		ops.append((i, 1))
	print(sum([(j - i) ** 2 for (i, j) in ops]))
	for (i, j) in ops:
		(p[i], p[j]) = (p[j], p[i])
	p = p[1:]
	print(' '.join(map(str, p)))
	print(len(ops))
	for (i, j) in ops[::-1]:
		print(i, j)


from __future__ import division, print_function
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	if n == 2:
		print('1 \n2 1 \n1 \n2 1')
		return
	if n == 3:
		print('5 \n2 3 1 \n2 \n1 3 \n2 3')
		return
	ans = [i for i in range(n + 1)]
	ans[1] = n - 1
	ans[2] = 1
	ans[-1] = 2
	ans[-2] = n
	order = [(1, n), (n - 1, 1), (2, n)]
	i = 3
	j = n - 2
	for _ in range((n - 4) // 2):
		(ans[i], ans[n]) = (ans[n], ans[i])
		order.append((i, n))
		(ans[j], ans[1]) = (ans[1], ans[j])
		order.append((j, 1))
		i += 1
		j -= 1
	if n % 2:
		(ans[i], ans[n]) = (ans[n], ans[i])
		order.append((i, n))
	out = 0
	for i in range(ceil(n / 2), n):
		if i == n - 1:
			out += (n - 1) * (n - 1)
		else:
			out += 2 * (i * i)
	if n % 2:
		out += n // 2 * (n // 2)
	print(out)
	print(' '.join((str(ans[i]) for i in range(1, len(ans)))))
	print(len(order))
	for i in range(len(order) - 1, -1, -1):
		print(*order[i])
testcase(int(inp()))


for _ in range(int(input())):
	n = int(input())
	a = list(range(1, n + 1))
	ans = (n - 1) ** 2
	for i in range(1, n - 1):
		ans += max(i, n - i - 1) ** 2
	pos = list(range(n - 1))
	pos.sort(key=lambda i: min(i, n - i - 1))
	ops = []
	for i in pos:
		if i * 2 < n:
			ops.append([i + 1, n])
			(a[i], a[n - 1]) = (a[n - 1], a[i])
		else:
			ops.append([i + 1, 1])
			(a[i], a[0]) = (a[0], a[i])
	print(ans)
	print(*a)
	print(len(ops))
	for (x, y) in ops[::-1]:
		print(x, y)


t = int(input())
for _ in range(t):
	n = int(input())
	c = 0
	for i in range(n // 2 + 1, n):
		c += (i - 1) ** 2
	for i in range(1, n // 2 + 1):
		c += (n - i) ** 2
	print(c)
	print(n // 2 + 1, end=' ')
	for i in range(1, n // 2):
		print(i, end=' ')
	for i in range(n // 2 + 2, n + 1):
		print(i, end=' ')
	print(n // 2)
	print(n - 1)
	for i in range(n // 2 + 1, n):
		print(i, 1)
	for i in range(n // 2, 0, -1):
		print(i, n)


import sys, io, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	A = [i for i in range(1, n + 1)]
	moves = []
	time = 0
	for i in range(1, n // 2 + 1):
		time += (i - n) ** 2
		moves.append((i, n))
		(A[i - 1], A[n - 1]) = (A[n - 1], A[i - 1])
	for i in range(n // 2 + 1, n):
		time += (i - 1) ** 2
		moves.append((i, 1))
		(A[i - 1], A[0]) = (A[0], A[i - 1])
	print(time)
	print(*A)
	print(len(moves))
	for move in reversed(moves):
		print(*move)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		if n <= 3:
			print((n - 1) * n * (2 * n - 1) // 6)
			print(' '.join(map(str, range(2, n + 1))) + ' 1')
			print(n - 1)
			for i in range(n - 1):
				print(str(i + 1) + ' ' + str(n))
		else:
			l = list(range(1, n + 1))
			ans = 0
			ans += (n - 1) * (n - 1)
			tmp = l[-1]
			l[-1] = l[0]
			l[0] = tmp
			ansL = [(1, n)]
			for i in range(1, n - 1):
				if i < n // 2:
					ans += (n - i - 1) * (n - i - 1)
					ansL.append((i + 1, n))
					tmp = l[i]
					l[i] = l[n - 1]
					l[n - 1] = tmp
				else:
					ans += i * i
					ansL.append((i + 1, 1))
					tmp = l[i]
					l[i] = l[0]
					l[0] = tmp
			ansL.reverse()
			print(ans)
			print(' '.join(map(str, l)))
			print(n - 1)
			for elem in ansL:
				print(str(elem[0]) + ' ' + str(elem[1]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
for CASES in range(int(input())):
	n = int(input())
	A = [i + 1 for i in range(n)]
	OP = []
	ans = 0
	l = 0
	r = n - 1
	tik = 0
	OP.append([l, r])
	ans += (r - l) * (r - l)
	(A[l], A[r]) = (A[r], A[l])
	for turn in range(n // 2 - 1):
		r -= 1
		l += 1
		OP.append([0, r])
		OP.append([n - 1, l])
		ans += (r - 0) * (r - 0) + (n - 1 - l) * (n - 1 - l)
		(A[0], A[r]) = (A[r], A[0])
		(A[l], A[n - 1]) = (A[n - 1], A[l])
	if n % 2 == 1:
		l += 1
		OP.append([0, l])
		ans += (l - 0) * (l - 0)
		(A[l], A[0]) = (A[0], A[l])
	print(ans)
	print(*A)
	print(len(OP))
	for i in range(len(OP) - 1, -1, -1):
		op = OP[i]
		print(op[1] + 1, op[0] + 1)


import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
	n = int(input())
	curr = list(range(1, n + 1))
	ops = []
	val = 0
	for i in range(n // 2, n):
		ops.append(f'{i + 1} 1')
		(curr[0], curr[i]) = (curr[i], curr[0])
		val += i * i
	for i in range(1, n // 2):
		ops.append(f'{i + 1} {n}')
		(curr[-1], curr[i]) = (curr[i], curr[-1])
		val += (n - 1 - i) * (n - 1 - i)
	ops.reverse()
	out.append(str(val))
	out.append(' '.join(map(str, curr)))
	out.append(str(len(ops)))
	out.append('\n'.join(ops))
print('\n'.join(out))