Alchembit Exam

시간 제한1초메모리 제한2048 MB

요약
인접한 포션 구간을 합치면서 그 구간의 비트 AND 값을 점수로 얻을 때, 얻을 수 있는 최대 점수를 구한다.
난이도

보통10점 중 7점

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

문제

As a modern alchemy student, you are taking an exam in Alchembit, a hybrid between alchemy and modern technology. In the exam, you are given NN potions (numbered from 11 to NN) where potion ii has a potency of an integer A_iA\_i. You start the exam with a score of 00.

You can increase your score by doing the following procedure.

  1. Suppose there are nn potions remaining. Choose an interval \[l,r]\[l, r] where 1≤l<r≤n1 ≤ l < r ≤ n.
  2. By choosing the interval \[l,r]\[l, r], your score will be increased by A\_l \\,\\&\\, A\_{l+1} \\,\\&\\, \dots \\,\\&\\, A\_r, where the symbol \\& represents the bitwise AND operator.
  3. Next, fuse potions l,l+1,…,rl, l + 1, \dots , r into one new potion with a potency of A\_l \\,\\&\\, A\_{l+1} \\,\\&\\, \dots \\,\\&\\, A\_r.
  4. The potions are then renumbered as follows: the newly fused potion becomes potion ll, and potions r+1,r+2,…,nr + 1, r + 2, \dots , n are renumbered as l+1,l+2,…,l+(n−r)l+ 1, l+ 2, \dots , l+ (n-r). Potions numbered 1,2,…,l−11, 2, \dots , l-1 remain unchanged.

For example, if you have 55 potions with potencies A=\[19,12,10,20,23]A = \[19, 12, 10, 20, 23], and you choose interval \[2,3]\[2, 3], then your score will be increased by 12 \\,\\&\\, 10 = 8. Then, potions 22 and 33 are fused into a new potion with a potency of 12 \\,\\&\\, 10 = 8. After the renumbering procedure (step 4), A becomes \[19,8,20,23]\[19, 8, 20, 23].

You can perform the above procedure until there is only one potion left. Determine the maximum score that you can achieve.

입력

The first line consists of an integer NN (2≤N≤100,0002 ≤ N ≤ 100\\, 000).

The second line consists of NN integers A_iA\_i (0≤A_i<2300 ≤ A\_i < 2^{30}).

출력

Output a single integer representing the maximum score that you can get.

예제2

  1. 예제 1

    입력
    5
    19 12 10 20 23
    
    예상 출력
    28
    
  2. 예제 2

    입력
    4
    1000000000 1000000000 1000000000 1000000000
    
    예상 출력
    3000000000