题目描述

对于一个序列 $a$，删除其中 $0$ 个或多个元素且不改变剩余元素相对顺序后得到的序列称为 $a$ 的子序列。

给定一个包含 $n$ 个非零整数的序列 $a$，请从中选取一个子序列，使其满足：

1. 子序列中相邻元素的正负号相反（即符号交替：正、负、正、负……或负、正、负、正……）；
2. 在满足条件 $1$ 的所有子序列中，长度尽可能长；
3. 在满足条件 $1$ 与条件 $2$ 的所有子序列中，元素之和尽可能大。

请输出该子序列的元素之和。

输入格式

第一行输入一个整数 $n$。
第二行输入 $n$ 个整数 $a_i$（以空格分隔）。

输出格式

输出一个整数，表示满足题目要求的子序列的元素之和。

样例输入输出

样例输入1

5
2 -1 -3 15 10

样例输出1

16

数据范围与测试点说明

• $1\le n\le 2\times 10^5$；
• $-10^9\le a_i\le 10^9$，且 $a_i\ne 0$。

时间限制与内存限制

• 时间限制：$1$ 秒
• 内存限制：$1024$ KiB