Bài tập về nhà

Xem PDF
Tác giả:
ngpin_04
Dạng bài
Điểm: 2400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau một ngày ăn chơi sinh nhật hết mình, Đôn về nhà và liền leo lên giường. Đột nhiên Đôn nhớ lại mình chưa làm bài tập môn Bitwise 101 dành cho trẻ mầm non. Đề bài ấy như sau:

Đề bài

Cho dãy số nguyên không âm \(a_1, a_2, \ldots, a_n\). Ta gọi dãy con liên \([l, r]\) là dãy tốt khi thoả mãn điều kiện sau:

\(a_l \ \& \ a_{l + 1} \ \& \ \ldots \ \& \ a_r > a_l \oplus a_{l + 1} \oplus \ldots \oplus a_r\)

Hay nói cách khác là tổng AND phải lớn hơn tổng XOR của các phần tử trong dãy con. Hãy tìm dãy con liên tiếp là dãy tốt dài nhất.

Đôn vì chơi sinh nhật quá hăng nên giờ chẳng còn tí sức nào để làm bài nữa. Hãy giúp Đôn nhé.

Input

  • Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)) là số lượng phần tử trong dãy.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 10^6\)) là giá trị của các phần tử trong dãy.

Output

  • Một số nguyên duy nhất là độ dài dãy con là dãy tốt dài nhất.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(a_i \leq 1\).
  • Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10^2\).
  • Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^3\).
  • Subtask \(4\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
1 0 1
Output 
0

Test 2

Input 
2
5 6
Output 
2

Test 3

Input 
6
8 1 3 3 1 2
Output 
4

Bình luận