Đội thợ săn kho báu của bạn vừa phát hiện ra một khu khảo cổ khổng lồ, chứa đầy kim loại quý và cổ vật giá trị. Khu vực này bao gồm $n$ điểm đào nằm trên một đường thẳng.

Các kế hoạch ban đầu cho thấy mỗi điểm trong số $n$ điểm đào đều có một lợi nhuận ròng đi kèm. Cụ thể, lợi nhuận của điểm thứ $i$ là $p_i$. Điều này có nghĩa là đội của bạn sẽ thu được $p_i$ đô la cho mỗi mét đào được tại điểm thứ $i$. Lưu ý rằng $p_i$ cũng có thể là số âm, nghĩa là chi phí vận hành máy móc đào vượt quá lợi nhuận thực tế thu được từ việc đào tại điểm thứ $i$.

Tất nhiên, bạn muốn đào càng nhiều càng tốt tại các điểm có lợi nhuận cao nhất. Tuy nhiên, để tránh sạt lở đất, bạn không được phép tạo ra các độ dốc quá lớn. Cụ thể hơn, với bất kỳ hai điểm đào liền kề nào, độ sâu đào tại các điểm này không được chênh lệch quá 1 mét. Đặc biệt, các điểm 1 và $n$ chỉ có thể được đào sâu tối đa 1 mét.

Lợi nhuận ròng lớn nhất mà bạn có thể đạt được dưới những điều kiện này là bao nhiêu?

Ví dụ, một kế hoạch đào hợp lệ và tối ưu cho trường hợp đầu tiên được minh họa dưới đây. Lợi nhuận ròng của kế hoạch này là 8.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $n$ ($1 \le n \le 250\,000$).

Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $p_i$ ($-10^6 \le p_i \le 10^6$), cách nhau bởi các dấu cách.

Dữ liệu ra

In ra duy nhất một số nguyên là lợi nhuận lớn nhất mà bạn có thể đạt được.

Ví dụ

Dữ liệu vào 1

5
1 3 -4 2 1

Dữ liệu ra 1

8

Dữ liệu vào 2

4
1 1 -2 3

Dữ liệu ra 2

5

Dữ liệu vào 3

5
-1 -3 0 -5 -4

Dữ liệu ra 3

0