Explanation

Let $|$ denote the bitwise OR operation and $\&$ denote the bitwise AND operation.

The answer is equivalent to finding an $x$ such that $x=a_j\&a_k$ and $a_i|x$ is maximized for some three indices $i<j<k$.

Note that $x$ can be binary searched since $2^b>2^0+2^1+\dots+2^{b-1}$, so we can loop through each $2^b$ in decreasing order and check if there exists an answer for $z$ such that $z$ is a superset of $x|2^b$. When we reach a bit $2^b$ such that it is contained in $a_i$, it doesn't matter whether it is in the final $x$ since $a_i|x$ already contains $2^b$.

In other words, we have to find a pair $(j, k)$ such that $i<j<k$ and $a_j\&a_k$ is a superset of $x|2^b$. This is equivalent to finding $j$ and $k$ such that $j, k>i$, $a_j\supseteq x|2^b$, and $a_k\supseteq x|2^b$. This can be done by Sum Over Subsets DP (or supersets in this case) by maintaining $f_x$ and $g_x$, which stores the two largest $j$ such that $a_j\supseteq x$.

Implementation

Time Complexity: $\mathcal{O}(N\log A + A\log A)$ where $A=\max a_i$.

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
const int B = 21;
const int A = 1 << B;

int main() {
	int n;
	cin >> n;