思路: 二进制枚举

用 $0$ 到 $2^{n}-1$ 这 $n$ 个数来表示选或不选，这样来构成一个子集。

这 $2^n$ 个数在二进制上可以看成是长度为 $n$ 的二进制位，那么第 $i$ 位为 $0$ 表示不选第 $i$ 个数，为 $1$ 表示选第 $i$ 个数。

如此就可以枚举 $0$ 到 $2^{n}-1$ ，然后再考虑每个数的每个二进制位，从而确定每个子集。

时间复杂度：$O(n\cdot 2^n)$

题目描述

小红有一个长度为 $n$ 的数组。

对于一个数组，小红定义这个数组的数组权值为每个元素的元素权值之和。

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

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

输入描述

第一行，一个正整数 $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