Problem 52: Maximum Bitwise OR Subarray

Problem Statement: Given an array of non-negative integers, determine the maximum bitwise OR obtainable from any non-empty contiguous subarray.

Input

The first line contains an integer n, the number of elements. The second line contains n space-separated non-negative integers.

Output

Print the maximum possible value obtained by the bitwise OR of all elements in some contiguous subarray.

Examples


Input:
5
1 2 4 0 3

Output:
7

Solution Explanation

A brute-force approach examines every subarray and computes its bitwise OR (O(n^2)). Optimization can be done using the idea that OR is cumulative; however, in worst-case scenarios an O(n^2) solution suffices given moderate constraints.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    cin >> n;
    vector a(n);
    for(int i = 0; i < n; i++) 
        cin >> a[i];
    int ans = 0;
    for(int i = 0; i < n; i++){
        int cur = 0;
        for(int j = i; j < n; j++){
            cur |= a[j];
            ans = max(ans, cur);
        }
    }
    cout << ans << "\n";
    return 0;
}