Loại Bỏ Một Phần Tử

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một hoán vị $p$ độ dài $n$ . Hãy loại bỏ đúng một phần tử khỏi hoán vị sao cho số kỷ lục (record) của dãy còn lại lớn nhất có thể.

Trong dãy $a_{1}, a_{2}, \dots, a_{k}$ , phần tử $a_{i}$ được gọi là một kỷ lục nếu với mọi chỉ số $j$ thoả $1 \leq j < i$ , ta có $a_{j} < a_{i}$ (tức $a_{i}$ lớn hơn mọi phần tử đứng trước nó). Theo định nghĩa, $a_{1}$ luôn là một kỷ lục.

Nếu có nhiều phần tử khi loại bỏ đều cho số kỷ lục lớn nhất, hãy in ra phần tử có giá trị nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — độ dài của hoán vị.
Dòng thứ hai chứa $n$ số nguyên phân biệt $p_{1}, p_{2}, \dots, p_{n}$ — hoán vị.

Dữ liệu ra

Một số nguyên duy nhất — phần tử cần loại bỏ.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq p_{i} \leq n$ và các $p_{i}$ đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
1 1	1	Chỉ có một phần tử để loại bỏ.
5 5 1 2 3 4	5	Khi loại bỏ $5$ , dãy còn lại $1 2 3 4$ có $4$ kỷ lục. Các cách loại bỏ khác đều cho ít kỷ lục hơn.
5 2 3 4 1 5	1	Loại bỏ $1$ cho dãy $2 3 4 5$ với $4$ kỷ lục — nhiều nhất có thể.

Bình luận

Không có bình luận tại thời điểm này.