CSES - Increasing Array II | Dãy tăng II - LQDOJ: Le Quy Don Online Judge

CSES - Increasing Array II | Dãy tăng II

Tác giả:

Dạng bài

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cung cấp 1 mảng gồm \(n\) số nguyên. Bạn muốn sửa lại giá trị của các phần tử để giá trị các phần tử trong mảng tăng dần, tức là mọi phần tử đều không bé hơn phần tử trước nó.
Trong mỗi lần thay đổi, bạn có thể tăng hoặc giảm giá trị của bất kỳ phần tử nào 1 đơn vị. Số lần thay đổi tối thiểu là bao nhiêu?

Input

Dòng đầu chứa số nguyên \(n\): kích thước của mảng.
Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) là các phần tử của mảng.

Output

In ra 1 số nguyên duy nhất là số lần thay đổi tối thiểu.

Constraints

\(1 \le n \le 2 \times 10^5\).
\(1 \le a_i \le 10^9\).

Example

Sample input

5  
3 8 5 6 5

Sample output

Bình luận

Thanh72 • 2:20 p.m. 19 Tháng 8, 2023 •
Bạn được cung cấp \(1\) mảng gồm \(n\) số nguyên. Bạn muốn sửa lại giá trị của các phần tử để giá trị các phần tử mảng tăng dần, tức là mọi phần tử đều không bé hơn phần tử trước nó.
Trong mỗi lần thay đổi, bạn có thể tăng hoặc giảm giá trị của bất kỳ phần tử nào \(1\) đơn vị. Số lần thay đổi tối thiểu là bao nhiêu?

Input

Dòng đầu chứa số nguyên \(n(1 \leq n \leq 2 \times 10^5)\).

Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)\) là các phần tử của mảng.

Output

In ra \(1\) số nguyên duy nhất là số lần thay đổi tối thiểu.

Example

Test 1

Input

5 3 8 5 6 5

Output

4

This comment is hidden due to too much negative feedback. Click here to view it.
-5
Phản hồi Chia sẻ