P5788 [Template] Monotonic Stack

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.

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 a_i} \{j\}$. If it does not exist, then $f(i)=0$. Find $f(1\dots n)$.

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

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

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