#include <bits/stdc++.h> #include "perm.h" using namespace std; using ll = long long; long long fact(int n){ long long r = 1; for (int i = 2; i <= n; i++) r *= i; return r; } #include <bits/stdc++.h> using namespace std; using ll = long long; struct Fenwick { int n; vector<ll> bit; Fenwick(int n = 0): n(n), bit(n+1, 0) {} void add(int idx, ll val){ for (; idx <= n; idx += idx & -idx) bit[idx] += val; } ll sumPrefix(int idx){ ll res = 0; for (; idx > 0; idx -= idx & -idx) res += bit[idx]; return res; } }; ll solve(const vector<int>& a){ int n = (int)a.size(); if (n == 0) return 1; Fenwick fw(n); ll total_non_empty = 0; for (int i = 0; i < n; ++i) { int val = a[i] + 1; ll sum_smaller = fw.sumPrefix(val - 1); ll dpi = sum_smaller + 1; fw.add(val, dpi); total_non_empty += dpi; } return total_non_empty + 1; } ll extra_subseq(int L){ ll power = 1; for (int i = 0; i < L; ++i) { power *= 2; } return power - L - 1; } vector<int> construct_permutation(long long k){ if (k<=1000){ vector <int> v; for (int i=k-2; i>=0; i--){ v.push_back(i); } return v; } vector <ll> f; f.push_back(0); int c=1; while (c<60){ f.push_back(extra_subseq(c)); c++; } ll cur=998; vector <int> v; while (k>1000){ for (int i=59; i>=0; i--){ if (k-f[i]>=1000){ k=k-f[i]; cur=cur-i+1; v.push_back(cur); cur--; break; } } } vector <int> vv; int tt=0,tp=998; while (tt<v.size()){ for (int i=v[tt]; i<=tp; i++){ vv.push_back(i); } tp=v[tt]-1; tt++; } for (int i=tp; i>=0; i--){vv.push_back(i);} return vv; }