暂无测试数据。

给你一个长度为 $n$ 的序列,请你求出去掉每个数的最长上升序列的长度是多少。

输入格式

第一行一个整数 $n$ 表示有 $n$ 个数。

接下来一行有 $n$ 个正整数，表示这个序列中的每一个数。

输出格式

输出 $n$ 个数，对于第 $i$ 个数，表示去掉第 $i$ 个数后最长上升序列的长度。

数据规模与约定

对于 $10\%$ 的数据，保证 $n \leq 10$

对于 $30\%$ 的数据，保证 $n \leq 100$

对于 $60\%$ 的数据，保证 $n \leq 3000$

对于 $100\%$ 的数据，保证 $n \leq 10^6$

5
1 3 2 4 5

3 4 4 3 3