题目描述

给定一个长度为$n$的数组，这个数组的数组权值为每个元素的元素权值之和。

对于数组中的第 $i$ 个元素，其元素权值为这个数组中，包含第 $i$ 个元素的所有子集中，所有元素之和大于等于 $0$ 的子集数量。

子集是数组所有非空子序列的集合，例如数组[1,2]的子集 有[1],[2],[1,2]

现在你需要输出这个数组的数组权值。

输入描述

第一行，一个正整数 $n(1\leq n\leq 18)$ ，表示数组的长度。

第二行，$n$个整数表示数组 $a$ ，第 $i$ 个元素为 $a_i(-10^9 \leq a_i \leq 10^9)$

数据保证每个 $a_i$ 都是不同的。

输出描述

一个整数，表示这个数组的数组权值。

样例

输入

3
1 2 -3

输出

7

说明

$a[1]$ 的元素权值为 $3$ 。([1], [1, 2], [1, 2, -3])

$a[2]$ 的元素权值为 $3$ 。([2], [1, 2], [1, 2, -3])

$a[3]$ 的元素权值为 $1$ 。([1, 2, -3])

故数组权值之和为 3+3+1=7