LINEGAME

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
Dạng bài
Điểm: 1000 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm \(n\) ô vuông, đánh số từ trái qua phải bắt đầu từ \(1\). Trên ô vuông thứ \(i\) người ta ghi một số nguyên dương \(a_i\), \(i = 1, 2, ..., n.\)

Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô \(i_1, i_2, ..., i_k\). Khi đó điểm số mà người chơi đạt được sẽ là: \(a_{i_1} - a_{i_2} + ... + (-1)^{k-1}a_{i_k}\).

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Input

  • Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 10^6)\) là số lượng ô của băng số;
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((a_i \leq 10^4, i = 1, 2, ..., n)\) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

  • Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Example

Test 1

Input 
7
4 9 2 4 1 3 7
Output 
17
Note

Bình luận