#P10159. 加减

加减

给定一个长度为 NN 的整数数组 AA(下标从 0 开始)。

考虑 AA 的一个长度为 KK 的子序列,元素的下标分别为 0≤i0<i1<i2<…<iK−1<N0 \le i_0 < i_1 < i_2 < \ldots < i_{K-1} < N,该子序列的价值被定为 ∑0≤t<K(−1)tAit\displaystyle \sum_{0 \le t < K} (-1)^tA_{i_t}.

现在,对于所有 1≤K≤N1 \le K \le N,请你求出长度为 KK 的子序列的最大价值。

输入格式

第一行一个整数 NN.

第二行 NN 个整数 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1}.

输出格式

输出 NN 行,每行一个整数,第 ii 行表示长度为 ii 的子序列的最大价值。

输入输出中相邻两个整数用空格隔开。

样例输入

7
100 10 10 100 64 75 359

样例输出

359 90 449 126 485 -11 348

样例解释

  • K=1:359K=1:359
  • K=2:100−10=90K=2:100-10=90
  • K=3:100−10+359=449K=3:100-10+359=449
  • K=4:100−10+100−64=126K=4:100-10+100-64=126
  • K=5:100−10+100−64+359=485K=5:100-10+100-64+359=485
  • K=6:100−10+10−100+64−75=−11K=6:100-10+10-100+64-75=-11
  • K=7:100−10+10−100+64−75+359=348K=7:100-10+10-100+64-75+359=348

子任务

对于所有数据,保证 1≤N≤5×105,−109≤Ai≤1091 \le N \le 5 \times 10^5,-10^9 \le A_i \le 10^9.

  1. N≤5000N \le 5000(15 分)
  2. 0≤Ai≤20 \le A_i \le 2(10 分)
  3. AiA_i 的种类数不超过 55(15 分)
  4. Ai≥1A_i \ge 1(20 分)
  5. N≤105N \le 10^5(20 分)
  6. 没有特殊性质(20 分)

时间限制:1s\texttt{1s}

空间限制:512MB\texttt{512MB}