Trò chơi 262144

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie đang chơi một trò chơi với dãy số. Cô ấy có một dãy gồm $N$ số nguyên dương, mỗi số có giá trị từ $1$ đến $40$ .

Trong một bước, Bessie có thể chọn hai phần tử liền kề trong dãy có cùng giá trị $v$ , rồi thay thế chúng bằng một phần tử có giá trị $v + 1$ . Thao tác này làm giảm độ dài dãy đi 1.

Bessie có thể thực hiện bất kỳ số bước nào. Hãy tìm giá trị lớn nhất có thể đạt được trong dãy sau khi thực hiện các thao tác.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng chứa một số nguyên là giá trị của phần tử tiếp theo trong dãy.

Dữ liệu ra

In ra một số nguyên duy nhất — giá trị lớn nhất có thể đạt được.

Ràng buộc

$1 \leq N \leq 262144$
Mỗi giá trị trong dãy nằm trong khoảng $[1, 40]$

Ví dụ

Input	Output	Giải thích
4 1 1 1 2	3	Ghép hai số `1` đầu tiên thành `2`, dãy thành `[2, 1, 2]`. Ghép hai số `2` ở vị trí 1 và 3 không hợp lệ vì không liền kề. Thay vào đó, ghép `1` và `2`... Thực ra: `[1,1,1,2]` → ghép vị trí 3,4 (`1,2` không bằng nhau), ghép vị trí 1,2 (`1,1`) → `[2,1,2]`. Hoặc: ghép vị trí 2,3 → `[1,2,2]` → ghép vị trí 2,3 → `[1,3]`. Giá trị lớn nhất là `3`.
20 1 1 2 1 1 1 1 2 1 1 2 2 29 27 27 27 27 29 28 28	31	Có thể ghép các phần tử để đạt giá trị `31`.

Ghi chú

Trong ví dụ 1: [1,1,1,2] → ghép 2 phần tử đầu → [2,1,2]. Rồi không thể ghép thêm theo cách này. Hoặc [1,1,1,2] → ghép phần tử 2 và 3 → [1,2,2] → ghép phần tử 2 và 3 → [1,3]. Giá trị lớn nhất trong dãy cuối cùng là 3.

Bình luận

Không có bình luận tại thời điểm này.