Problem D
Gurkburkar

Det finns $N$ burkar med inlagda gurkor på din hylla, och du vill samla alla gurkor i en enda burk.

Du kan först omordna burkarna i valfri ordning. För att överföra gurkor väljer du två intilliggande burkar. Därefter flyttar du alla gurkor från den vänstra burken till den högra burken och tar sedan bort den vänstra burken. Du fortsätter att överföra gurkor tills endast en enda burk återstår.

Du kan fritt välja den ursprungliga ordningen på burkarna och hur du kombinerar dem. Beroende på hur denna process genomförs kommer du att få olika mängder av smakrikhet i den slutliga burken med gurkor.

Varje burk $i$ har ett saltlakevärde $a_i$. När du flyttar gurkor från burk $j$ till burk $i$, ökar smakrikheten hos den slutliga satsen gurkor med $a_i \oplus a_j$, där $\oplus $ definieras som bitvis XOR ¹.

Den bitvisa XOR-operationen mellan två heltal $x$ och $y$ beräknas genom att jämföra de binära representationerna av $x$ och $y$. Den $i$:te biten av $x \oplus y$ är 1 om och endast om exakt en av de $i$:te bitarna i $a$ och $b$ är 1. Bitvis XOR finns som en operator i både C++ och Python som ^.

Som en gurkkännare vill du maximera den totala smakrikheten efter alla operationer. Hitta en ordning av burkarna och en ordning av överföringar som maximerar den totala smakrikheten.

Indata

Den första raden av indata innehåller heltalet $N$ ($1 \leq N \leq 5 \cdot 10^5$), antalet burkar med gurkor.

Den följande raden innehåller $N$ mellanskillnadsseparerade heltal $a_0, a_1, \dots , a_{N-1}$ ($1 \leq a_i \leq 10^{12}$), som beskriver saltlakevärdena för gurkburkarna.

Utdata

Först ska du skriva ut ett heltal: den maximala möjliga smakrikheten som kan uppnås.

För att få full poäng behöver du även skriva ut en permutation och en ordning av sammanslagningar som uppnår denna smakrikheten. Om du får $75\% $ av poängen för en viss deluppgift räcker det att endast skriva ut smakrikheten.

På den andra raden, skriv ut permutationen av burkarna. Det $i$:te heltalet är indexet för burken som ska placeras på position $i$.

På den tredje raden, skriv ut heltalen $p_1, p_2, \dots , p_{N-1}$ som beskriver ordningen av överföringarna. Först, anta att burkarna har blivit omordnade enligt din permutation och sedan ommärkta från $0$ till $N-1$ från vänster till höger. Därefter betyder varje $p_i$ att vid överföring nummer $i$, så är den vänstra burken burk nummer $p_i$. Observera att efter att burkar tas bort, ommärks inte de återstående burkarnas index.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I exempel 1 placerar vi gurkburkarna i ordningen $[2,5,1]$. Vi överför sedan burk $0$ till burk $1$, vilket lägger till en smakrikhet på $2 \oplus 5=7$. Slutligen överför vi burk $1$ till burk $2$, vilket lägger till en smakrikhet på $5 \oplus 1=4$, vilket resulterar i $7+4=11$ total smakrikhet. Det finns fler än ett sätt att uppnå denna smakrikheten.

I exempel 2 räcker det att använda den ordning som ges i indata. Överföringarna sker enligt följande:

• Överför burk $0$ till burk $1$, vilket lägger till smakrikhet $5 \oplus 2=7$. De återstående burkarna har saltlakevärden $[2,2,5]$.

• Överför burk $2$ till burk $3$, vilket lägger till smakrikhet $2 \oplus 5=7$. De återstående burkarna har saltlakevärden $[2,5]$.

• Överför burk $1$ till burk $3$, vilket lägger till smakrikhet $2 \oplus 5=7$. Den kvarvarande burken har saltlakevärden $[5]$.

Detta resulterar i $7+7+7=21$ total smakrikhet. Återigen finns det fler än ett sätt att uppnå denna smakrikheten.

3
1 2 5

11
1 2 0 
0 1 

4
5 2 2 5

21
0 1 2 3
0 2 1

6
10 2 15 12 3 2

65
1 2 5 3 4 0 
1 2 0 3 4