Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

hide comments
2018-10-29 08:46:10
Test : 7 4 4 5 4 7
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.