B-四边形不等式_2020 CCPC Wannafly Winter Camp Day7 Div.1＆2（重现赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在本题中，我们用区间 ${[x,y]}$ 表示 $x,x+1,\ldots,y$ 这 ${y-x+1}$ 个正整数。对于一个 ${n}$ ，我们称一个定义在所有 ${[1,n]}$ 的子区间（即 $1\le x\le y\le n$ 的区间 ${[x,y]}$ ）上的函数 ${f}$ 满足四边形不等式，当对于任何的 $1\le i\le j\le k\le l\le n$ ，有 $f([i,k])+f([j,l])\ge f([i,l])+f([j,k])$ （即如果两个区间有交且不严格包含，则两个区间的函数值的和大于等于它们的交的函数值加上并的函数值），且对于任意的 $1\le i\le j< l\le n$ 有 $f([i,j])+f([j+1,l])\ge f([i,l])$ （即如果两个区间相邻，则它们的函数值的和大于等于它们的并的函数值的和）。

我们可以扩展 ${f}$ 的定义域，使其在所有的 $[n]=\{1,\ldots,n\}$ 的子集上都有定义，且满足四边形不等式。具体地说，一个定义在所有 ${[n]}$ 子集上的函数 ${f}$ 满足四边形不等式，当 $\forall X\subseteq[n], Y\subseteq[n], f(X)+f(Y)\ge f(X\cap Y)+f(X\cup Y)$ 。

给定一个定义在区间上满足四边形不等式的函数，试将其扩展到 ${[n]}$ 的所有子集上。

输入描述:

第一行包含一个正整数 （）。
接下来  行，第  行包含  个非负整数，依次表示 。函数值都是  到  之间的整数。

输出描述:

输出一行  个非负整数，不超过 ，依次表示每个  的子集的函数值，其中子集按照字典序排列。集合  在字典序中排在  前面，当  中最大的元素仅在  中出现。对于所有的 ， 必须与输入保持一致。

示例1

输入

复制

输出

复制

0 3 3 2 3 6 2 1