Số đảo tối đa

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $N$ ô đất xếp thành dãy, ô thứ $i$ có độ cao $H_{i}$ . Nước dâng đều từ dưới lên. Khi mực nước bằng độ cao của một ô, ô đó chìm xuống. Một đảo là đoạn ô liên tiếp chưa chìm.

Tìm số đảo tối đa có thể quan sát được tại bất kỳ thời điểm nào trong quá trình ngập lụt.

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ .
$N$ dòng tiếp: Độ cao $H_{i}$ của ô thứ $i$ .

Dữ liệu ra

Một số nguyên — số đảo tối đa.

Ràng buộc

$1 \leq N \leq 100000$
$1 \leq H_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
8 3 5 2 3 1 4 2 3	4	Khi nước ở mức 1, ô 5 chìm, còn lại 4 đảo.
6 2 2 1 2 2 1	2	Khi mực nước=1, ô 3 và 6 chìm → 2 đảo.

Bình luận

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