答案
最大权值：
\[\begin{cases}
\lfloor \frac{n+1}{2} \rfloor \cdot n,\; n\text{为奇数}, \\
\lfloor \frac{n+1}{2} \rfloor \cdot (n+1),\; n\text{为偶数},
\end{cases}
\]
把列 A：从 n 到 1 倒序输出
思路
题目转换：原题目就是在求，对于某个排列 A 及其所有循环同构，一共能得到多少个连通块
设所有得到的连通块放在集合 S 内
由于每个数字都会在每一位上出现一次，所以在自己位置上出现且仅出现一次，所以可以想到 S 内有且仅有 n 个自环，其他的均不是自环
每个序号在 S 内出现且仅出现 n 次
这样，考虑是否能使除了自环外，其余每个连通块都只含两个元素
我们这样假设，如下，上面一行是固定的 i，下面是会移动的 A 内的 \(a_i\)，对于
... a ... b ...
... b ... a ...
对于下一步操作，会把下面的往右移一位，这时如果还要保证还是都是两顶点连通块，画一下就可以得到
... a x ... b y ...
... y b ... x a ...
注意观察，这里上下正好是反序，不防试下从 n 到 1 的排法，发现能满足要求，那这就是最优解
至于权值的公式，我是找规律猜的（笑哭
代码
#include <bits/stdc++.h>
#define EVAL(...) __VA_ARGS__
#define overload4(a, b, c, d, e, ...) EVAL(e)
#define rep3(_i, _st, _ed) for (int _i = (_st); _i <= (_ed); ++_i)
#define rep2(_i, _ed) EVAL(rep3(_i, 1, _ed))
#define rep1(_ed) EVAL(rep2(i, _ed))
#define rep4(_i, _st, _ed, _step) for (int _i = (_st); _i <= (_ed); _i += (_step))
#define rep(...) EVAL(overload4(__VA_ARGS__, rep4, rep3, rep2, rep1))(__VA_ARGS__)
#define per3(_i, _st, _ed) for (int _i = (_st); _i >= (_ed); --_i)
#define per2(_i, _st) EVAL(per3(_i, _st, 1))
#define per1(_st) EVAL(per2(i, _st))
#define per4(_i, _st, _ed, _step) for (int _i = (_st); _i >= (_ed); _i -= (_step))
#define per(...) EVAL(overload4(__VA_ARGS__, per4, per3, per2, per1))(__VA_ARGS__)
#define ft first
#define sd second
template <typename A, typename B>
constexpr bool chmin(A &a, const B &b) noexcept
{if (a > b){a = static_cast<A>(b);return true;}else{return false;}
}
template <typename A, typename B>
constexpr bool chmax(A &a, const B &b) noexcept
{if (a < b){a = static_cast<A>(b);return true;}else{return false;}
}
using namespace std;
using ll = long long;
using pii = pair<int, int>;void solve();int main()
{cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin >> t;while (t--){solve();}return 0;
}void solve()
{int n;cin >> n;const int tmp = (n + 1) / 2;int ans = tmp * n;if (!(n & 1)){ans += tmp;}cout << ans << '\n';per(n){cout << i << ' ';}cout << '\n';
}