Description

Bob is an ACMer of ZJUT, he wanted to increase his energy by eating AC-APPLEs.

There are N(1 <= N <= 150,000) AC-APPLEs, each AC-APPLE had a magic value "v" which is a positive integer and not bigger than 500.

Bob visited AC-APPLEs which are given in order, every time he faced an AC-APPLE, he can choose "eat this one" or "pass this one". The odd time Bob ate, he increases v units energy. The even time Bob ate, he decreases v units energy.

Before eating any AC-APPLE, Bob's energy is 0.

Please calculate the Maximum Energy Bob can increase by eating AC-APPLEs.

Input

The input will consist of more than one data set.

Each data set has two lines. First line has an integer N. Second line has N integers which means the magic value of each AC-APPLEs.

Output

the Maximum Energy Bob can increase

Sample

Input

8
7 2 1 8 4 3 5 6

Output

17

Source: BobKing