Hàm số một lần nữa

Cho một mảng $a$ gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$. Với mỗi cặp chỉ số $l,r$ thỏa $1\le l<r\le n$, định nghĩa hàm

$$f(l,r)=\sum _{i=l}^{r-1}(-1{)}^{i-l}|a_i-a_{i+1}|=|a_l-a_{l+1}|-|a_{l+1}-a_{l+2}|+|a_{l+2}-a_{l+3}|-\cdots$$

Nói cách khác, trên đoạn từ $l$ đến $r$ ta lấy tổng các giá trị tuyệt đối của hiệu hai phần tử liên tiếp, với dấu xen kẽ bắt đầu bằng dấu cộng.

Hãy tính giá trị lớn nhất của $f(l,r)$ trên tất cả các cặp $(l,r)$ hợp lệ.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$ là kích thước mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất là giá trị lớn nhất của hàm $f$.

Ràng buộc

• $2\le n\le {10}^5$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ