Background

This is a template problem, with no background.

Testdata was updated on 2019.12.12. The time limit was relaxed, and it no longer relies on constant-factor optimizations.

Problem Description

Given an integer sequence $a_{1 \dots n}$ with $n$ terms.

Define a function $f(i)$ as the index of the first element after the $i$-th element in the sequence that is greater than $a_i$, that is, $f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}$. If it does not exist, then $f(i)=0$.

Find $f(1\dots n)$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_{1\dots n}$.

Output Format

Output one line with $n$ integers representing the values of $f(1), f(2), \dots, f(n)$.

5
1 4 2 3 5

2 5 4 5 0

Hint

Constraints

For $30\%$ of the testdata, $n\leq 100$.

For $60\%$ of the testdata, $n\leq 5 \times 10^3$.

For $100\%$ of the testdata, $1 \le n\leq 3\times 10^6$, $1\leq a_i\leq 10^9$.

Translated by ChatGPT 5