Problem C: pipi的二维偏序

Problem C: pipi的二维偏序

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 133  Solved: 53
[Submit] [Status] [Web Board] [Creator:]

Description

pipin个整数a_1,a_2,...,a_n,对于i=1,2,...,npipi想知道满足1\le j<ia_j<a_i的最大a_j是多少,如果没有输出-1

Input

第一个输入一个整数n(1\le n\le 300000)
第二行n个整数a_1,a_2,...,a_n(1\le a_i\le 10^9)

Output

输出一行n个整数,为i=1,2,...,n时的答案。

Sample Input

6
2 3 5 4 6 2

Sample Output

-1 2 3 3 5 -1