← 返回题目列表

AtCoder · arc207_c

C. 组合起来使非减

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个长度的整数序列 N, A=(A_1, A_2, \cdots, A_N)。 斯努克想要制作 A 非递减序列。

他可以执行以下操作零次或多次。

  • 选择两个相邻元素 A
  • 删除这两个元素并按位插入 原始位置的这两个值的 \mathrm{OR} 原始位置的这两个值的

找出长度的最大可能值 A 当 A 变为非递减序列。

什么是按位 \mathrm{OR}?

按位 \mathrm{OR} 非负整数 A 和 B, A\ \mathrm{OR}\ B定义如下。

  • 当 A\ \mathrm{OR}\ B 以二进制形式写入,其中的数字 2^k 地点(k \geq 0) 是 1 如果至少有一位数字 2^k 地点 A 和 B 写成二进制是 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 成立。

约束

  • 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-st 和 2-nd 元素在第一个操作中选择, A=(3,2) 和 A 不是非递减序列。
  • 如果 2-nd 和 3-rd 元素在第一个操作中选择, 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