아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Bank Security Unification

시간 제한2초메모리 제한512 MB

요약
라우터들의 부분 수열을 골라 인접한 값들의 비트 AND 합이 최대가 되도록 한다.
난이도

보통10점 중 7점

유형
동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

The Bytelandian government has issued the Bank Security Unification law (or, shortly, the BSU law). The recent law regulates the usage of Wi-Fi routers in banks and other financial institutions.

According to the BSU law, all the nn Wi-Fi routers in a bank must be located in a straight line. Suppose that the ii-th router operates at the frequency f_if\_i. Denote the security of a connection between two adjacent routers as f\_{i}\\,\\, \\&\\,\\, f\_{i+1}, where \\& is the bitwise AND operation.

A set of at least two routers numbered 1≤i_1<i_2<⋯<i_k≤n1 \le i\_1 < i\_2 < \dots < i\_k \le n must be chosen as active.  All other routers will be kept inactive so that they can replace the active ones if any of them would break. Denote the security of the network as the sum of the securities of all connections between adjacent active routers. In other words, the security of the network is calculated as \sum\limits\_{j=1}^{k-1} f\_{i\_j}\\,\\,\\&\\,\\,f\_{i\_{j+1}}.

You are an employee of a large Bytelandian bank. Surely, the bank is obliged to comply with the BSU law. The routers are already placed in a line, and their placement cannot be changed. Now you want to choose some of the routers as active to maximize the security of the network.

입력

The first line contains an integer nn, denoting the number of Wi-Fi routers in the bank (2≤n≤1062 \le n \le 10^6).

The second line contains nn integers f_1,f_2,…,f_nf\_1, f\_2, \ldots, f\_n, where f_if\_i is the frequency of the ii-th router in the line (0≤f_i≤10120 \le f\_i \le 10^{12}).

출력

Print the maximum possible security of the network.

예제2

  1. 예제 1

    입력
    5
    1 2 3 1 3
    
    예상 출력
    5
    
  2. 예제 2

    입력
    4
    1 2 4 0
    
    예상 출력
    0