C - Combine to Make Non-decreasing 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

長さ N の整数列 A=(A_1, A_2, \cdots, A_N) が与えられます。 すぬけ君は A が広義単調増加列になるようにしたいです。

すぬけ君は 0 回以上以下の操作を行うことができます。

  • A の隣接する 2 つの要素を選ぶ
  • この 2 つの要素を取り除き、代わりにこの 2 つのビット単位 \mathrm{OR} を取った値を元の位置に挿入する

A が広義単調増加列となったときの長さとしてありうる値の最大値を求めてください。

ビット単位 \mathrm{OR} 演算とは

非負整数 A, B のビット単位 \mathrm{OR}、A\ \mathrm{OR}\ B は以下のように定義されます。

  • A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。
例えば、3\ \mathrm{OR}\ 5 = 7 となります (二進表記すると: 011\ \mathrm{OR}\ 101 = 111)。

広義単調増加列とは

数列 a=(a_1,a_2, \cdots, a_n) が a_1 \le a_2 \le \ldots \le a_n を満たすとき、またそのときに限り、a は広義単調増加列であるといいます。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i <2^{30}
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 1 2

出力例 1

2
  • 1 回目の操作で 1 番目と 2 番目の要素を選んだ場合 A=(3,2) となり A は広義単調増加列ではありません。
  • 1 回目の操作で 2 番目と 3 番目の要素を選んだ場合 A=(3,3) となり A は広義単調増加列となります。

入力例 2

4
4 1 2 3

出力例 2

1

入力例 3

20
105327673 847116534 928167271 478716741 244808645 744985167 772409400 950055714 32441819 24475691 74630537 632066724 170250355 937572655 791196964 469960355 264764288 1061830134 183233398 643628719

出力例 3

7

Score : 800 points

Problem Statement

You are given an integer sequence of length N, A=(A_1, A_2, \cdots, A_N). Snuke wants to make A a non-decreasing sequence.

He can perform the following operation zero or more times.

  • Choose two adjacent elements of A
  • Remove these two elements and insert the bitwise \mathrm{OR} of these two values at the original position

Find the maximum possible value of the length of A when A becomes a non-decreasing sequence.

What is bitwise \mathrm{OR}?

The bitwise \mathrm{OR} of non-negative integers A and B, A\ \mathrm{OR}\ B, is defined as follows.

  • When A\ \mathrm{OR}\ B is written in binary, the digit in the 2^k place (k \geq 0) is 1 if at least one of the digits in the 2^k place of A and B written in binary is 1, and 0 otherwise.
For example, 3\ \mathrm{OR}\ 5 = 7 (in binary: 011\ \mathrm{OR}\ 101 = 111).

What is a non-decreasing sequence?

A sequence a=(a_1,a_2, \cdots, a_n) is a non-decreasing sequence if and only if a_1 \le a_2 \le \ldots \le a_n holds.

Constraints

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i <2^{30}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 1 2

Sample Output 1

2
  • If the 1-st and 2-nd elements are chosen in the first operation, A=(3,2) and A is not a non-decreasing sequence.
  • If the 2-nd and 3-rd elements are chosen in the first operation, A=(3,3) and A is a non-decreasing sequence.

Sample Input 2

4
4 1 2 3

Sample Output 2

1

Sample Input 3

20
105327673 847116534 928167271 478716741 244808645 744985167 772409400 950055714 32441819 24475691 74630537 632066724 170250355 937572655 791196964 469960355 264764288 1061830134 183233398 643628719

Sample Output 3

7