Chú ếch và hòn đá 1

Tác giả:

Dạng bài

Điểm: 200 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) hòn đá được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), chiều cao của hòn đá thứ \(i\) là \(h_i\)

Có một con ếch ban đầu ở hòn đá \(1\). Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá \(N\).

Nếu con ếch đang ở hòn đá \(i\), thì nó có thể nhảy sang hòn đá thứ \(i+1\) hoặc \(i+2\) với chi phí là \(|h_i-h_j|\), trong đó \(j\) là vị trí nó muốn nhảy tới.

Tìm chi phí tối thiểu để nó đến được hòn đá thứ \(N\).

Dòng thứ nhất chứa số nguyên \(N(2\le N\le 10^5)\)
Dòng thứ hai chứa \(N\) số nguyên : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Test 1

Input

4
10 30 40 20

Output

Note

Giải thích: Con ếch sẽ nhảy như sau: \(1\rightarrow 2 \rightarrow 4\), với chi phí là \(|10-30|+|30-20|=30\)

Bình luận