Background

This problem only supports C++ submissions. When submitting, you do not need to include the perm.h header file. You only need to paste the content of perm.h from the attachment at the beginning of your code.

Problem Description

Pharaohs use the gravity of planets to accelerate spaceships. Suppose a spaceship will fly by $n$ planets in order with orbital speeds $p[0], p[1],\dots, p[n - 1]$. When flying by each planet, the Pharaoh scientists may choose whether to use it to accelerate the spaceship. To save energy, after the spaceship flies by a planet with orbital speed $p[i]$ and accelerates, it can no longer accelerate when later flying by a planet with orbital speed $p[j] < p[i]$. In other words, the planets chosen for acceleration form an increasing subsequence of $p[0], p[1],\dots, p[n - 1]$. A subsequence of $p$ is a sequence obtained by deleting zero or more elements from $p$. For example, $[0]$, $[ ]$, $[0, 2]$, and $[0, 1, 2]$ are subsequences of $[0, 1, 2]$, but $[2, 1]$ is not.

The scientists have confirmed that there are a total of $k$ different ways to choose planets to accelerate the spaceship, but they have lost the record of orbital speeds (even the value of $n$). However, they remember that $(p[0], p[1],\dots, p[n - 1])$ is a permutation of $0, 1,\dots, n - 1$. Here, a permutation is a sequence that contains every integer from $0$ to $n - 1$ exactly once. Your task is to find such a permutation $(p[0], p[1],\dots, p[n - 1])$ with the smallest possible length that satisfies the requirement.

You need to solve this problem for $q$ different spaceships. For each spaceship $i$, you are given an integer $k_i$, which is the number of different ways to choose planets to accelerate the spaceship. Your task is to find an orbital speed sequence of sufficiently small length $n$, such that there are exactly $k_i$ increasing subsequences that can be chosen from it.

Implementation Details

You need to implement the following function:

int[] construct_permutation(int64 k)

• $k$ is the required number of increasing subsequences.
• The function should return an array of $n$ elements, where each element is a number between $0$ and $n - 1$ (inclusive).
• The returned array must be a valid permutation with exactly $k$ increasing subsequences.
• This function will be called a total of $q$ times. Each call is considered an independent scenario.

Input Format

The sample grader reads input in the following format:

• Line $1$: $q$.
• Line $2+i$ ($0\le i\le q-1$): $k_i$.

Output Format

For each $k_i$, the sample grader prints one line containing the return value of the corresponding construct_permutation call. If an error occurs, it prints an error message.

2
3
8

2
1 0
3
0 1 2

Hint

Examples

Example $1$

Consider the following call:

construct_permutation(3)

The function should return a permutation that has exactly $3$ increasing subsequences. One possible answer is $[1,0]$, whose increasing subsequences are $[]$ (the empty subsequence), $[0]$, and $[1]$.

Example $2$

Consider the following call:

construct_permutation(8)

The function should return a permutation that has exactly $8$ increasing subsequences. One possible answer is $[0,1,2]$.

Constraints

• $1\le q\le 100$.
• $2\le k_i\le 10^{18}$ (for all $0\le i\le q-1$).

Subtasks

1. ($10$ points) $2\le k_i\le 90$ (for all $0\le i\le q-1$). If all permutations you output have length at most $90$ and are correct, you will get $10$ points; otherwise, you will get $0$ points.
2. ($90$ points) No additional constraints. For this subtask, let $m$ be the maximum length among the permutations you output across all scenarios. Your score is computed according to the table below:

Input Format

Output Format

Hint

Translated by ChatGPT 5