JIJ 编程竞赛 2026（第 476 场 AtCoder Beginner Contest）
第三大的数AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given an integer $N$ not less than $3$ and a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$.
给定一个不小于 $3$ 的整数 $N$，以及一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。AI (CI翻译)
For each $k=3,4,\ldots,N$, solve the following problem:
对于每个 $k=3,4,\ldots,N$，请解决以下问题：AI (CI翻译)
- When
$A_1,A_2,\ldots,A_k$are sorted in descending order, find the third value from the front.
- 将
$A_1,A_2,\ldots,A_k$按降序排列，求排列后的第三个数。
Constraints
约束条件
AI (CI翻译)$3\le N\le 5\times 10^5$$1\le A_i\le 10^9$- All input values are integers.
$3\le N\le 5\times 10^5$$1\le A_i\le 10^9$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
A_1 A_2 \ldots A_NN
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Output $N-2$ lines.
输出 $N-2$ 行。AI (CI翻译)
The $i$-th line $(1\le i\le N-2)$ should contain the answer for $k=i+2$.
第 $i$ 行 $(1\le i\le N-2)$ 应包含 $k=i+2$ 时的答案。AI (CI翻译)
样例
Input #1
5
1 2 1 2 3
Output #1
1
1
2
- For $k=3$: sorting $A_1,A_2,A_3$ in descending order gives $2,1,1$. The third value from the front is $1$, so output $1$ on the first line.
- For $k=4$: sorting $A_1,A_2,A_3,A_4$ in descending order gives $2,2,1,1$. The third value from the front is $1$, so output $1$ on the second line.
- For $k=5$: sorting $A_1,A_2,A_3,A_4,A_5$ in descending order gives $3,2,2,1,1$. The third value from the front is $2$, so output $2$ on the third line.
Input #2
10
1 1 1 3 2 5 4 3 6 5
Output #2
1
1
1
2
3
3
4
5
Input #3
10
11 9 1 3 17 19 10 19 17 3
Output #3
1
3
9
11
11
17
17
17
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。