| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P162SUMD - Round 2D - Thuốc tăng trưởng |
PTIT mới được phủ xanh bằng một hàng cây mới. Hàng cây gồm n cây với chiều cao khác nhau, chính vì thế mà hàng cây trông rất lộn xộn. Học viện quyết định sẽ sắp xếp lại các cây để được một thứ tự không giảm về chiều cao. Tất nhiên việc đào các cây lên vào trồng lại sẽ rất mất thời gian và chi phí vì thế Học viện chọn cách sẽ dùng thuốc tăng trưởng để tăng chiều cao cho các cây.
Mỗi một lần phun thuốc thì chỉ có thể phun liên tiếp từ cây thứ i đến cây thứ j trên hàng cây, và mỗi cây sẽ tăng lên thêm một đơn vị chiều cao. Vậy cần phải phun ít nhất bao nhiêu lần thì ta sẽ được 1 hàng cây có thứ tự không giảm.
Input
Dòng đầu tiên gồm số nguyên N (1 <= N <= 10^5) là số cây.
Dòng tiếp theo là N số nguyên a[i] (1 <= a[i] <= 10^9) là chiều cao của mỗi cây.
Output
In ra số nguyên duy nhất là số lần phun ít nhất.
Example
Input: 5
5 4 4 3 6 Output: 2
Giải thích:
Phun lần 1: chỉ phun ở cây 4 => ta được 5 4 4 4 6
Phun lần 2: phun từ cây 2 đến cây 4 => ta được 5 5 5 5 6
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-14 |
| Thời gian chạy: | 1s-2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
