Cho ~n~ ngôi nhà được xếp thành một vòng (nghĩa là nhà ~1~ và nhà ~n~ cũng liền kề nhau) và mỗi nhà đều có số tiền nhất định.

Bạn là một tên trộm thông minh, nhưng không thể trộm hai nhà liền kề nhau.

Hãy tìm số tiền lớn nhất bạn có thể trộm được sao cho không trộm hai nhà liền kề nhau.

Yêu cầu:Tính số tiền mà bạn có thể trộm nhiều nhất.

Input

• Dòng thứ nhất chỉ có một số nguyên dương ~n~ - số lượng nhà (~1 \leq n \leq 10^6~).
• Dòng thứ hai có ~n~ số nguyên dương ~a_1,a_2,...,a_n~ - ~a_i~ số tiền của nhà thứ ~i~ (~1 \leq a_i \leq 10^9~).

Output

Một số nguyên duy nhất — số tiền lớn nhất mà tên trộm có thể lấy được khi các ngôi nhà xếp thành vòng tròn.

Example input 1

4
2 3 2 5

Example output 1

8