#2328. 第一个大的数字

第一个大的数字

题目描述

对于一个 1 到 n 的排列 p(即 1 到 n 中每一个数在 p 中出现了恰好一次),令 qiq_i 为第 ii 个位置之后第一个比 pip_i 值更大的位置,如果不存在这样的位置,则 qi=n+1q_i =n+1。举例来说,如果 n=5 且 p 为 1 5 4 2 3,则 q 为 2 6 6 5 6。

输入格式

第一行一个正整数 nn

第二行 nn 个正整数 p1np_{1\dots n} ,保证1 到 n 中的每个数字只出现一次。

输出格式

一行 nn 个整数 f(1n)f(1\dots n) 的值。

样例

输入样例

5
1 5 4 2 3

输出样例

2 6 6 5 6

数据范围与提示

对于 30%30\% 的数据,n100n\leq 100

对于 60%60\% 的数据,n5×103n\leq 5 \times 10^3

对于 100%100\% 的数据,1n3×1061 \le n\leq 3\times 10^6