410034: GYM103921 F Bit Paths

There are $$$n$$$ cities in BIT Land, where the $$$i$$$th city has value $$$a_i$$$. Between every pair of cities, there is a road paved with rocks. The cost to travel from city $$$i$$$ to city $$$j$$$ over the rocky road is $$$a_i \& a_j$$$, where $$$\&$$$ is the bitwise AND operator.

Some of these distances are large, so you discovered an alternative route. Each city $$$i$$$ has a corresponding city in the mirror universe TIB Land. The value of each city in TIB Land, $$$b_i$$$, is the value you get when flipping the lowest $$$32$$$ bits of $$$a_i$$$. Between each pair of cities is a road paved with avocados. The cost to travel from city $$$i$$$ to city $$$j$$$ over the avocado-y road is $$$b_i \& b_j$$$. There is a portal between city $$$i$$$ in BIT Land and city $$$i$$$ in TIB Land, so there is no cost traveling between the two universes.

You want to make a delivery of rocks and avocados starting at city $$$1$$$ and ending at city $$$n$$$, both in BIT Land. You want to minimize the total cost of your path, which is computed by summing the cost of each edge you travel on. What is the minimum cost that you would have over any path?

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2000$$$) — the number of cities.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 2^{32} - 2$$$) – the value of each city in BIT Land.

Print a single integer — the shortest distance from city $$$1$$$ in BIT Land to city $$$n$$$ in BIT Land.

3
1 2 1

0

2
4294967294 4294967292

1