CSUOJ

Problem1635--中位数之和（10分）

1635: 中位数之和（10分）

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 128 MB

Solved: 0 Submit: 442 Statistics

Description

$median(a,b,c)$ 返回 $a,b,c$ 三个数的中间数，如 $median(1,2,3)$ 返回 $2$ , $median(4,3,8)$ 返回 $4$ ， $median(2,5,5)$ 返回 $5$ 。
给出一个长度为 $n$ 个数组 $a_1,a_2,...,a_n$ 。
求 $median(a_1,a_2,a_3)+median(a_2,a_3,a_4)+median(a_3,a_4,a_5)+...+median(a_{n-2},a_{n-1},a_n)$

Input

第一行输入 $1$ 个整数 $n(3\le n\le 100000)$
第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le 10^9)$

Output

输出一行一个整数表示答案。

Sample Input Copy

10
1 3 2 4 1000000000 998244353 666666666 999999999 999999999 888888888

Sample Output Copy

4994733066

HINT

$median(1,3,2)=2$
$median(3,2,4)=3$
$median(2,4,1000000000)=4$
...

$median(999999999,999999999,888888888)=999999999$
求和得 $4994733066$ ，注意求和后可能超出 $int$ 范围

Source/Category

Submit