Cho dãy số nguyên gồm N phần tử ~a_1,a_2,…,a_N.~ Yêu cầu: Chọn ra một tập gồm các phần tử trong dãy (tập hợp có thể rỗng) sao cho không có hai phần tử nào kề nhau và có tổng các số trong tập hợp là lớn nhất có thể. In ra tổng của tập hợp tìm được (nếu là tập rỗng thì tổng bằng 0).

Input:
    Dòng đầu gồm duy nhất một số nguyên dương N (~N≤〖10〗^5~ );
    Dòng thứ hai gồm N phần tử ~a_1,a_2,…,a_N  (1<|a_i |≤〖10〗^9 ).~
Output: In ra kết quả bài toán.

input         utput

3
4 5 6          10