Bobo learned how to compute Longest Increasing Subsequence (LIS) in O(nlogn) in ICPCCamp.
For those who did not attend ICPCCamp as Bobo, recall LIS(a₁, a₂, . . . , a_n) is defined as f[1]² ⊕ f[2]² ⊕· · · ⊕ f[n]² where ⊕ denotes the exclusive-or (XOR) and f is calculated as follows.
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)
Given sequence A = (a₁, a₂, . . . , a_n), Bobo would like to find LIS(B₁), LIS(B₂), . . . , LIS(B_n) where B_i is the sequence after removing the i-th element from A.

The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains an integer n. The second line contains n integers a₁, a₂, . . . , a_n.
• 2 ≤ n ≤ 5000
• 1 ≤ a_i ≤ n
• The number of test cases does not exceed 10.

For each case, output n integers which denote LIS(B₁), LIS(B₂), . . . , LIS(B_n).

5
2 5 3 1 4

5 13 0 8 0

2017年四川省赛