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.|

P186SUMG - ROUND 6G - Đánh dấu mảng số

Cho một mảng A[] có kích thước N. Một phần tử có thể đánh đấu dược khi mà nó lớn hơn cả phần tử liền trước và liền sau của nó (nếu có tồn tại).

Ví dụ, với mảng {4, 9, 1, 3}; “9” và “3” là các phần tử có thể đánh dấu.

Trên mảng, ta có thể thực hiện 1 thao tác: thao tác này lựa chọn 1 phần tử trên mảng và giảm nó đi 1 đơn vị.

Hãy cho biết, với 1 <= k <= ceil(N/2); với ceil(x) là số x được làm tròn lên thành số nguyên (ví dụ: ceil(0.4) = 1); ta cần thực hiện ít nhất bao nhiêu thao tác để có thể đánh dấu được k phần tử?

Input

Dòng đầu tiên chứa một số nguyên N (1 <= N  <= 5000), chỉ kích thước mảng A[].

Dòng thứ hai chứa N số nguyên A_i, là các phần tử của A[] (1 <= A_i <= 10^5).

Output

In ra ceil(N/2) số nguyên, cách nhau bằng dấu cách. Số thứ i biểu diễn số thao tác ít nhất cần thực hiện lên mảng để có thể đánh dấu được i phần tử trên mảng.

Example

Input:
5
1 1 1 1 1
Output:
1 2 2
Input:
3
1 2 3
Output:
0 2
Input:
5
1 2 3 2 2
Output:
0 1 3

Được gửi lên bởi:adm
Ngày:2018-08-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.