Những bức tranh đẹp

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.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

Có $n$ bức tranh được mang đến triển lãm. Bức thứ $i$ có độ đẹp $a_{i}$ . Một khách tham quan trở nên vui mỗi khi đi từ một bức tranh sang một bức đẹp hơn nghiêm ngặt (tức là chuyển từ bức có độ đẹp $x$ sang bức có độ đẹp $y$ với $y > x$ ).

Bạn được phép sắp xếp các bức tranh theo thứ tự tuỳ ý. Khách sẽ đi qua tất cả các bức tranh từ trái sang phải đúng một lần. Hãy tìm số lần khách trở nên vui lớn nhất có thể.

Nói cách khác: hãy sắp xếp lại dãy $a$ và tìm số lượng lớn nhất các chỉ số $i$ ( $1 \leq i \leq n - 1$ ) sao cho $a_{i + 1} > a_{i}$ .

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ — số bức tranh.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — độ đẹp của từng bức tranh.

Dữ liệu ra

In ra một số nguyên — số cặp liền kề $(a_{i}, a_{i + 1})$ thoả $a_{i + 1} > a_{i}$ lớn nhất sau khi sắp xếp tối ưu.

Ràng buộc

$1 \leq n \leq 1000$
$1 \leq a_{i} \leq 1000$

Ví dụ

Input	Output	Giải thích
5 20 30 10 50 40	4	Sắp xếp tối ưu: $10, 20, 30, 40, 50$ . Mọi cặp liền kề đều tăng nên có $4$ lần khách vui.
4 200 100 100 200	2	Sắp xếp tối ưu: $100, 200, 100, 200$ . Hai cặp $(100, 200)$ ở vị trí $1 - 2$ và $3 - 4$ tăng, còn cặp giữa $(200, 100)$ thì giảm.

Bình luận

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