Một công trình xây dựng có n thanh bờ tường chiều rộng bằng 1, chiều cho ai được dựng kề nhau. Các thanh bê tông được đánh số từ 1 đến n, khối bê tông thứ i có chiều cao ai (ai là các số nguyên dương). Lúc đầu các thanh bê tông này tạo thành một khối, nhà thầu xây dựng muốn dùng một tấm che chiều cao h (h là một số thực) để che các thanh bê tông từ dưới đất lên và các thanh bê tông cao hơn h sẽ nhìn thấy được, các thanh bê tông có độ cao nhỏ hơn hoặc bằng h sẽ không nhìn thấy được. Các thanh nhìn thấy được liên tiếp nhau sẽ tạo thành một khối. Nhà thầu xây dựng muốn nhờ bạn tính độ cao h bằng bao nhiêu để số khối bê tông nhìn thấy là nhiều nhất.
|
Dữ liệu cho trong file BETONG.INP như sau:
- Dòng đầu ghi số nguyên dương n.
- n dòng tiếp theo, mỗi dòng ghi một số nguyên ai chiều cao của thanh bê tông thứ i.
Kết quả ghi ra file BETONG.OUT gồm một số duy nhất là số khối bê tông nhiều nhất có thể tạo ra.
Ví dụ
-
input7
5
6
1
3
2
9
8output3
Giới hạn:
- 20% số test ứng với n ≤ 103, ai ≤ 109;
- 20% số test khác ứng với n ≤ 105 và ai ≤ 20;
- 20% số test khác ứng với n ≤ 105, ai ≠ aj với i ≠ j, ai ≤ 109;
- 20% số test khác ứng vớin ≤ 106,ai ≠ aj với i ≠ j, ai ≤ 109;
- 20% số test còn lại ứng vớin ≤ 106,ai ≤ 109;