题目描述

希蒙知识点大家今天学了LIS，所以他想验证下哪些人上课在摸鱼，现有n $(5 <= H <= 5000)$个数字，数字大小 $(1 <= a_i <= 1000)$，现需要倒着计算出整个序列的最长不上升序列，并将每个位置能够形成的最长序列值进行输出

输入格式

第一行: 两个由空格隔开的整数: n

第二行：n个数字

输出格式

第一行: 如题所述结果

样例

输入样例

14
13 7 9 16 38 24 37 18 44 19 21 22 63 15

输出样例

7 8 7 6 3 4 3 5 2 4 3 2 1 1

输入样例2

6
1 2 3 4 4 5

输出样例2

6 5 4 3 2 1