Santa Chunbae's Gift Distribution

Interview

Time limit1sMemory limit1024 MB

Summary

Given N gifts priced from 0 to 3, pair them into N/2 pairs so that the sum of the XOR values of the pairs is as large as possible.

Level: Medium5 of 10
Topics: Greedy, Implementation
Solved: No attempts yet

Problem

Santa Chunbae

Santa Chunbae is sorting gifts for baby cats. There are $N$ gifts in total, and Chunbae gives two gifts each to $\frac{N}{2}$ baby cats. $N$ is even.

Each gift has a price, and every price is an integer from $0$ to $3$ . The satisfaction a baby cat gets from its two gifts is the XOR of their prices. For example, gifts priced $1$ and $2$ give satisfaction $1$ XOR $2 = 3$ , and gifts priced $3$ and $3$ give satisfaction $3$ XOR $3 = 0$ .

Chunbae wants to hand out the gifts so that the total satisfaction is as large as possible. Write a program that computes this maximum total satisfaction.

Input

The first line contains $N$ , the number of gifts Chunbae has. $(2 \le N \le 200\,000,\ N$ is even $)$

The second line contains the prices of the $N$ gifts, separated by spaces. Every price is an integer from $0$ to $3$ .

Output

Print the maximum total satisfaction that Chunbae can get by giving out the gifts to the baby cats.

Hint

You can check the definition of XOR here.

Examples2

Example 1
Input
```
6
0 1 2 3 2 3
```
Expected output
```
7
```
Example 2
Input
```
2
3 3
```
Expected output
```
0
```