小红的双排列删除得分
题号：NC296659
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小红拿到了一个长为 2\times n 的双排列 \{a_{1},a_{2},...,a_{2\times n}\} 。
\hspace{15pt}小芳能帮他进行任意次如下操作：
\hspace{23pt}\bullet选择一个首尾元素相等的区间 \left[l,r\right]\left(1 \leqq l < r \leqq 2 \times n;\ a_{l} = a_{r}\right) ，将 a_{l},a_{l+ 1},...,a_{r} 这段元素删除，并将其余元素按现有顺序拼接起来，同时小红将获得 \sum\limits_{i = l}^{r}{a_{i}} 分。 
\hspace{15pt}请你帮小红求出可能的最高得分。

【名词解释】
\hspace{15pt}双排列：长度为 2\times n 的双排列为两个长度为 n 的排列打乱顺序后得到的数组。
\hspace{15pt}排列：长度为 n 的排列是由 1,2,\dots,n 这 n 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，\{2,3,1,5,4\} 是一个长度为 5 的排列，而 \{1,2,2\} 和 \{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1\leqq n \leqq 2\times 10^{5}\right)。
\hspace{15pt}第二行输入 2 \times n 个整数 a_{1},a_{2},...,a_{2\times n}\left(1 \leqq a_{i} \leqq n\right)，表示双排列的元素。保证其是一个合法的双排列。

输出描述:

\hspace{15pt}输出一个整数，代表最高得分。
示例1

输入

复制 
2
1 2 1 2

输出

复制 
5