Ếch 1 (Frog 1)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ phiến đá có độ cao $h_i$. Ếch bắt đầu ở đá 1 và mỗi lần được nhảy sang đá kế tiếp hoặc cách một đá. Chi phí của một lần nhảy từ $i$ đến $j$ là $|h_i-h_j|$. Hãy tìm tổng chi phí nhỏ nhất để tới đá $N$.

Input

Dòng 1 chứa $N$. Dòng 2 chứa $N$ số nguyên $h_1,h_2,\ldots,h_N$.

Output

In một số nguyên là tổng chi phí nhỏ nhất.

Subtask

• Subtask 1 — 20 điểm: 2 <= N <= 20. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 2 <= N <= 2000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 2 <= N <= 100000; 1 <= h_i <= 10000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

4
10 30 40 20

Output

30

Giải thích

Một phương án tối ưu là đi $1\to2\to4$, có chi phí $|10-30|+|30-20|=30$.