Kuroni and Antihype
Contest: Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)
Difficulty rating: 3500
Tags: bitmasks, brute force, dp, dsu, graphs

Kuroni isn't good at economics. So he decided to found a new financial pyramid called Antihype. It has the following rules:

1. You can join the pyramid for free and get $$$0$$$ coins.
2. If you are already a member of Antihype, you can invite your friend who is currently not a member of Antihype, and get a number of coins equal to your age (for each friend you invite).

$$$n$$$ people have heard about Antihype recently, the $$$i$$$-th person's age is $$$a_i$$$. Some of them are friends, but friendship is a weird thing now: the $$$i$$$-th person is a friend of the $$$j$$$-th person if and only if $$$a_i \text{ AND } a_j = 0$$$, where $$$\text{AND}$$$ denotes the bitwise AND operation.

Nobody among the $$$n$$$ people is a member of Antihype at the moment. They want to cooperate to join and invite each other to Antihype in a way that maximizes their combined gainings. Could you help them?

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n \le 2\cdot 10^5$$$)  — the number of people.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 2\cdot 10^5$$$)  — the ages of the people.

Output format:
Output exactly one integer  — the maximum possible combined gainings of all $$$n$$$ people.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Only the first and second persons are friends. The second can join Antihype and invite the first one, getting $$$2$$$ for it.

Example input:
3
1 2 3

Example output:
2

Editorial:
Let's forget about the structure of our graph of friendship first and let's solve a more general problem: what are the highest possible total gainings of all people given some edges.
Firstly, let's suppose there is a $$$n+1$$$-th person with age $$$a_{n+1} = 0$$$ in Antihype already, who is friend with everybody. We can suppose that instead of someone joining Antihype for free, he is invited by this person.
Now, let's color the edge between $$$i$$$ and $$$j$$$ in red if $$$a_i$$$ invited $$$a_j$$$ or $$$a_j$$$ invited $$$a_i$$$. Note that red edges form a tree. Let's write on an edge between $$$i$$$ and $$$j$$$ $$$a_i + a_j$$$.
Surprising fact: For a given tree $$$G$$$ of invitations, the total gainings are equal to the sum of numbers on the edges of the tree - sum of all $$$a_i$$$!
Proof:  Suppose that the degree of person $$$i$$$ in $$$G$$$ is $$$v_i$$$. Then this person was invited once and invited $$$v_i - 1$$$ times, giving $$$a_i(v_i - 1)$$$ coins in total. $$$\sum_{i = 1}^{n+1} a_i(v_i - 1) = \sum_{i = 1}^{n+1} a_i\cdot v_i - \sum_{i = 1}^{n+1} a_i = \sum_{(i, j)\in G} (a_i + a_j) - \sum_{i = 1}^{n+1} a_i$$$.
Now the solution is easy: on each edge $$$(i, j)$$$, write $$$a_i + a_j$$$ on it, find Maximum Spanning Tree, and subtract sum of $$$a_i$$$.
The $$$n+1$$$-th person works out well in out version of the problem: he is friend of everybody as $$$a_{n+1}\text{ AND }a_i = 0\text{ AND }a_i = 0$$$. However, we can't find MST directly, as there can be $$$\Omega(n^2)$$$ edges. There are two approaches now:
Approach 1:
Find MST with Borůvka's algorithm. Let's do $$$\log{n}$$$ iterations of the following:
For each mask, find two largest present weights (from different components) which are submasks of this mask in $$$O(2^{18} \cdot 18)$$$ with SOS DP. Then, for each component we can find the edge from this component to some other component with the largest weight, and do one iteration of Boruvka. Complexity $$$O(2^{18} \cdot 18 \cdot log(n)$$$).
Approach 2:
Make a list of people with each age first. Now, for $$$i$$$ from $$$2^{18} - 1$$$ to $$$0$$$, iterate through submasks of $$$i$$$, let it be $$$j$$$, and make edges between people with ages $$$j$$$ and $$$i\text{ XOR }j$$$, this edge will have weight of $$$i$$$. This works in $$$O(3^{18}\cdot\alpha(n))$$$, which is fast enough to pass.