题目描述

小红有一个长度为 $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