Description

一年一度的top竞赛又要开始了(听说由某个很出名的外企举办)，美丽聪明的小S打算拿个大奖去嫁给高富帅，但是问题是在是太难了，请你帮帮她吧。举办方准备了一个数组，数组相邻的两个一样的字符可以消掉并将其值加入总分。帮她获得最大分数吧

Format

Input

第一行输入一个n(n<=100000)，代表数组有n个元素。

第二行输入n个数，a1,a2,a3...an。值小于100000.

Output

输出得分的最大值。

Samples

8
1 2 3 4 4 3 2 1

10

Hint