← 返回题目列表

AtCoder · past22_k

K. 大手前

中文机器翻译题面 查看原题

问题陈述

给你一个正整数 N 和排列 A=(A_1,A_2,\dots,A_N) of (1,2,\dots,N)。 找出以下每个值 i=1,2,\dots,N:

  • 最大整数 j 这样 1 \leq j < i 和 A_j > A_i 如果这样的整数存在,或者 -1 否则。

约束

  • 1 \leq N \leq 5 \times 10^5
  • A 是一个排列 (1,2,\dots,N).

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印以下问题的答案 i=1,2,\dots,N 按此顺序,中间有空格。


示例输入 1

4
3 1 4 2

示例输出 1

-1 1 -1 3
  • i=1:否 j 满足条件,所以答案是 -1.
  • i=2: j=1 满足条件,所以答案是 1.
  • i=3:否 j 满足条件,所以答案是 -1.
  • i=4: j=1,3 满足条件,所以答案是 3,其中较大的一个。

示例输入 2

7
3 7 2 1 6 5 4

示例输出 2

-1 -1 2 3 2 5 6