n 個の整数からなる数列 a₁ … aₙ が与えられる。
各位置 i について、i より右（j > i）にあって aᵢ より大きい（等しいのはだめ）数のうち最も近いもの aⱼ を求めよ。
そのような数がなければ -1 とする。
n 個の答えを位置の順に空白区切りで一行に出力せよ。
一行目に n、二行目に a₁ … aₙ が空白区切りで与えられる。
7 2 7 3 5 4 6 8
7 8 5 6 6 8 -1
5 4 4 1 4 9
9 9 4 9 -1
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
位置ごとに右側を走査すると、減少する数列で n²/2 = 5 千万回比べます。
C・C++ は耐えますが、Craykon は実行ステップ上限（約 5 千万）を超えて止まり、Python も数秒かかります。
スタックに「まだ大きい数に出会っていない位置」を積んでおき、新しい数 x が来たら、一番上の値が x より小さい間取り出して答えを x と書き、最後に x の位置を積みます。
各位置は一回積んで一回取り出すので全部で 2n 回です。
罠は三つ：取り出す条件を <= にすると等しい数を「大きい数」とみなします（問題は <）。
「最初の大きい数」は「右側で最大の数」とは違います（1 5 3 4 で 3 の答えは 5 ではなく 4）。
そしてスタックには値ではなく位置を積むと答えをその場所に書けます。
スタックの使い方：Python リスト append()/pop()/stack[-1]、JavaScript・TypeScript 配列 push()/pop()/stack[stack.length - 1]（TS は pop() が number | undefined なので ! を付けます）、Java ArrayDeque の push()/pop()/peek()（古い Stack クラスより推奨）、C# Stack<int> の Push()/Pop()/Peek()、C++ std::stack の top()/pop()（pop() は値を返さないので先に top() を読みます）、C は配列と top 変数。
Craykon はリストの末尾を一番上として使い、stack[stack.個数 - 1] で見て stack.位置で取り除く(stack.個数 - 1) で取り出します。
n = int(input())a = list(map(int, input().split())) answer = [-1] * nstack = [] # 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for i, x in enumerate(a): while stack and a[stack[-1]] < x: # x가 그 자리들의 '오른쪽 첫 큰 수' answer[stack.pop()] = x stack.append(i)print(" ".join(map(str, answer)))const [n, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer = new Array(n).fill(-1);const stack = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import { readFileSync } from "node:fs";const [n, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); const answer: number[] = new Array(n).fill(-1);const stack: number[] = []; // 아직 더 큰 수를 못 만난 자리들. 값은 아래에서 위로 줄어든다(같을 수는 있다)for (let i = 0; i < n; i++) { while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) { answer[stack.pop()!] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i);}console.log(answer.join(" "));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); int[] answer = new int[n]; Arrays.fill(answer, -1); Deque<Integer> stack = new ArrayDeque<>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && a[stack.peek()] < a[i]) { answer[stack.pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.push(i); } StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(answer[i]); System.out.println(out); }}using System;using System.Collections.Generic;using System.Linq; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int[] answer = Enumerable.Repeat(-1, n).ToArray(); var stack = new Stack<int>(); // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (stack.Count > 0 && a[stack.Peek()] < a[i]) { answer[stack.Pop()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' } stack.Push(i); } Console.WriteLine(string.Join(" ", answer)); }}#include <iostream>#include <stack>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; std::vector<int> answer(n, -1); std::stack<int> st; // 아직 더 큰 수를 못 만난 자리들 for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] < a[i]) { answer[st.top()] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' st.pop(); } st.push(i); } for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << answer[i]; std::cout << '\n';}#include <stdio.h> #define MAXN 10000 int main(void) { static int a[MAXN], answer[MAXN], stack[MAXN]; int n, top = 0; /* stack[0..top-1]: 아직 더 큰 수를 못 만난 자리들 */ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { answer[i] = -1; while (top > 0 && a[stack[top - 1]] < a[i]) { answer[stack[--top]] = a[i]; /* a[i]가 그 자리의 '오른쪽 첫 큰 수' */ } stack[top++] = i; } for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", answer[i]); putchar('\n'); return 0;}n = コンソール.行読み().数に();a = コンソール.数読み(); answer = 新リスト(n, -1);stack = []; // 아직 더 큰 수를 못 만난 자리들. 맨 위는 stack[stack.개수 - 1]繰り返す (i = 0; i < n; i++){ 間 (stack.個数 > 0 && a[stack[stack.個数 - 1]] < a[i]) { answer[stack[stack.個数 - 1]] = a[i]; // a[i]가 그 자리의 '오른쪽 첫 큰 수' stack.位置で取り除く(stack.個数 - 1); } stack.追加(i);}コンソール.書く(answer);