#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;
}
