LIS

Cerință

Alec Sdima pregătește o problemă pentru Stelele Informaticii. El dorește să construiască o permutare care să aibă un număr foarte specific de subșiruri crescătoare de lungime maximă.

$\\[0.25cm]$

O permutare de lungime $N$ este o secvență $P[0], \ldots, P[N - 1]$ în care fiecare număr de la $1$ la $N$ apare exact o singură dată.

$\\[0.25cm]$

Un subșir al lui $P$ este o secvență $P[i_0], P[i_1], \ldots, P[i_{k-1}]$, unde $0 \leq i_0 < i_1 < \ldots < i_{k-1} < N$.

$\\[0.25cm]$

Un subșir este crescător dacă $P[i_0] < P[i_1] < \ldots < P[i_{k-1}]$. Un cel mai lung subșir crescător (LIS) este un subșir crescător de lungime maximă.

$\\[0.25cm]$

Alec alege un număr $K$. Trebuie să determini o permutare $P$ care să aibă exact $K$ cele mai lungi subșiruri crescătoare distincte. Două cele mai lungi subșiruri crescătoare sunt considerate distincte dacă folosesc mulțimi diferite de indici. Lungimea permutării determinate trebuie să fie de cel mult
$100 \ 000$.

Date de intrare

Prima linie conține $T$, numărul de test case-uri.

$\\[0.25cm]$

Următoarele $T$ linii conțin câte un număr $K$, reprezentând numărul necesar de cele mai lungi subșiruri crescătoare.

Date de ieșire

Pentru fiecare test case, afișați două linii.

$\\[0.25cm]$

Prima linie trebuie să conțină $N$, lungimea permutării determinate.

$\\[0.25cm]$

A doua linie trebuie să conțină o permutare $P[0], P[1], \ldots, P[N - 1]$ a numerelor de la $1$ la $N$.

Exemplu

Date de intrare

3
1
4
6

Date de ieșire

1
1
4
2 1 4 3
5
2 1 5 4 3

Pentru al treilea test case, să considerăm permutarea $[2, 1, 5, 4, 3]$.

$\\[0.25cm]$

Cele 6 cele mai lungi subșiruri crescătoare sunt:

Restricții și precizări

• $T \leq 10$
• $1 \leq K \leq 10^{18}$

Dacă secvența afișată nu are exact $K$ cele mai lungi subșiruri crescătoare sau dacă lungimea secvenței depășește $10^5$, punctajul obținut pentru testul respectiv va fi $0$.

Subtask 1 (10 puncte)

Vei primi 10 puncte dacă lungimea secvenței tale este de cel mult $120$, respectiv $0$ puncte în caz contrar.

Subtask 2 (30 de puncte)

Fie $L$ lungimea secvenței determinate de tine.

$\\[0.25cm]$

Dacă $L \leq 41$, vei primi punctajul maxim. În caz contrar, punctajul obținut pentru acest subtask este determinat de următoarea formulă:

Subtask 3 (60 de puncte)

Fie $L$ lungimea secvenței determinate de tine și fie

Dacă $L \leq 148$, vei primi punctajul maxim. În caz contrar, punctajul obținut pentru acest subtask este determinat de următoarea formulă: