Cho dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Một dãy con (có thể không liên tiếp) của dãy đã cho ~a_{b[1]}, a_{b[2]}, \dots, a_{b[k]}~ với ~b[i] < b[i+1]~ với mọi ~i = 1 \dots k-1~ có trọng số được định nghĩa bằng biểu thức: ~W = \sum_{i=1}^{\lceil k/2 \rceil} a_{b[2i-1]} - \sum_{i=1}^{\lfloor k/2 \rfloor} a_{b[2i]}~ Hay ~W = a_{b[1]} - a_{b[2]} + a_{b[3]} - a_{b[4]} + \dots~

Yêu cầu: Hãy tìm dãy con (có thể không liên tiếp) của dãy đã cho có trọng số lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \le 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \le 10^9~, ~i = 1 \dots n~).

Output

• Đưa ra một số nguyên là kết quả tìm được.