Bobo 在 ICPCCamp 学会了如何以 $O(n \log n)$ 的时间复杂度计算最长上升子序列（LIS）。

对于那些没有像 Bobo 一样参加 ICPCCamp 的人，回顾一下 $\mathrm{LIS}(a_1, a_2, \dots, a_n)$ 的定义为 $f[1]^2 \oplus f[2]^2 \oplus \dots \oplus f[n]^2$，其中 $\oplus$ 表示异或（XOR），而 $f$ 的计算方式如下：

for i in [1, 2, ..., n]
  f[i] = 1
  for j in [1, 2, ..., i - 1]
    if a[j] < a[i] then
      f[i] = max(f[i], f[j] + 1)

给定序列 $A = (a_1, a_2, \dots, a_n)$，Bobo 想要找到 $\mathrm{LIS}(B_1), \mathrm{LIS}(B_2), \dots, \mathrm{LIS}(B_n)$，其中 $B_i$ 是从 $A$ 中移除第 $i$ 个元素后得到的序列。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

• $2 \leq n \leq 5000$
• $1 \leq a_i \leq n$
• 测试用例数量不超过 $10$。

输出格式

对于每个测试用例，输出 $n$ 个整数，分别表示 $\mathrm{LIS}(B_1), \mathrm{LIS}(B_2), \dots, \mathrm{LIS}(B_n)$。

样例

样例输入 1

5
2 5 3 1 4

样例输出 1

5 13 0 8 0