题目描述

对于一个长度为奇数的数组，将其排序后值位于中间的数称为该数组的中位数。

现在给你一个长度为 n 的数组，你的任务是求出所有长度为奇数的子数组的中位数之和。

输入格式

第一行一个正整数 n，表示数组中有 n 个数。

接下来一行 n 个正整数，依次表示该数组。

输出格式

一行一个整数，表示给定数组中所有长度为奇数的子数组的中位数之和。

输入输出样例 #1

输入 #1

4
2 3 1 4

输出 #1

15

说明/提示

对于100%的数据，$1≤n≤2000$