Permutation Modified Version

Construct a permutation whose increasing-subsequence count matches the target value.

Solution Interface

Submit a zip_project solution. The run command is executed once per case, reads the case from standard input, and writes the answer to standard output. The trusted separated evaluator runs the migrated Frontier-CS Testlib checker against the submitted output and the case's evaluator-only answer or scoring metadata.

Scoring

The leaderboard score is the average checker ratio scaled to 0..100 across official cases. Invalid outputs receive zero for the affected case. The public validation case is intentionally tiny and deterministic; official scoring uses the source-derived Frontier-CS cases packaged as private benchmark data.

Original Statement

Permutation (Modified Version)

Time Limit: 5 s Memory Limit: 1024 MB

The Pharaohs use the relative movement and gravity of planets to accelerate their spaceships. Suppose a spaceship will pass by some planets with orbital speeds in order. For each planet, the Pharaohs' scientists can choose whether to accelerate the spaceship using this planet or not. To save energy, after accelerating by a planet with orbital speed p[i], the spaceship cannot be accelerated using any planet with orbital speed p[j] < p[i]. In other words, the chosen planets form an increasing subsequence of p.

The scientists have identified that there are exactly k different ways a set of planets can be chosen to accelerate the spaceship. They have lost their record of all the orbital speeds (even the value of n). However, they remember that p is a permutation of {0, 1, …, n−1}. Your task is to find one possible permutation of sufficiently small length.

Input The first line contains an integer q (1 ≤ q ≤ 100), the number of spaceships. The second line contains q integers k1, k2, …, kq (2 ≤ ki ≤ 10^18).

Output For each ki, output two lines:

• The first line contains an integer n (the length of the permutation).
• The second line contains n integers: a valid permutation of {0, 1, …, n−1} having exactly ki increasing subsequences.

Scoring Let m be the maximum permutation length you used across all queries. Your score for the test file will be determined as follows:

m ≤ 90 → 100 points

90 < m < 2000 -> linear function

m >= 2000 -> 0

Example Input 2 3 8

Output 2 1 0 3 0 1 2

Explanation For k = 3, one valid permutation is [1, 0], which has exactly 3 increasing subsequences: [], [0], [1]. For k = 8, one valid permutation is [0, 1, 2], which has exactly 8 increasing subsequences: [], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2].