1511: 抢红包2

新的一年到了，又到了激动人心的抢红包时刻。

小红、小蓝、小黄三个入一起抢红包，每一轮选出三个未被选的最大的红包，三个入依次出手，选取自己最想要的红包，每个红包最多被一个入获得，且每一轮每个入都会拿到一个红包。每一个红包的价值为 $ a_i $ 。

小红是一个低调的入，为了使自己不那么引人注目，小红需要根据上一轮的表现决定自己该轮怎么选。

1. 如果小红上一轮拿的红包是三入中最大的，则这一轮只能拿最小的。

2. 如果小红上一轮拿的红包是三入中最小的，则这一轮他可以随意拿的。

3. 如果小红上一轮拿的红包是三入中第二大的，则这一轮他不能拿最大的。

拿红包的顺序为小红、小蓝、小黄。且每个入都按最优的策略来拿。

问小红最多可以拿到的红包价值之和。

第一行输入一个 $ n $  $( 3 \le n \le 3 \cdot 10 ^ 5 $, 且保证  $ n $ 是 $ 3 $ 的倍数 $ ) $ -- 表示红包的数量。

第二行输入 $ n $ 个整数 $ a_i $ $ ( $  $ 1 \le a_i \le 10^9 $ , 且保证各个 $a_i$ 互不相同 $ ) $ -- 第 $i$ 个红包的价值。

输出一个整数表示小红最多可以拿到的红包价值之和。

6
6 1 10 13 11 2

16