Hai giá trị lớn nhất phân biệt

Bối cảnh

Một hệ thống xếp hạng nhận n điểm số và cần xác định hai mức điểm cao nhất phân biệt để chia hai nhóm thưởng. Nếu điểm cao nhất xuất hiện nhiều lần, nó vẫn chỉ được tính là một mức; mức thứ hai phải nhỏ hơn thực sự. Nếu toàn bộ dữ liệu chỉ có một giá trị phân biệt, hệ thống phải báo NO.

Bài toán tưởng giống tìm max, nhưng thêm yêu cầu "phân biệt" khiến state phức tạp hơn: trong quá trình duyệt, bạn phải biết liệu max1 và max2 đã tồn tại hay chưa, cập nhật đúng khi gặp một giá trị lớn hơn max1, nằm giữa max1 và max2, hoặc trùng với một giá trị đã biết. Bài yêu cầu recursion để duyệt mảng; mỗi tầng xử lý đúng một phần tử và cập nhật hai ứng viên qua tham chiếu. Không được dùng sort hay STL vì các nội dung đó thuộc Module 05. Đây là mẫu xử lý top-k nhỏ thường xuất hiện trong bài thi khi cần O(n) và không được phép sắp xếp.

Yêu cầu

1. Đọc n và mảng.
2. Dùng recursion duyệt từng phần tử.
3. Tìm giá trị lớn nhất và lớn thứ hai phân biệt.
4. Nếu có ít hơn 2 giá trị phân biệt, in NO.
5. Ngược lại in max1 max2.

Yêu cầu tổ chức code

Phần duyệt mảng và cập nhật hai cực trị phải bằng recursion.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Dòng 1 n. Dòng 2 n số.

Output

NO hoặc một dòng max1 max2.

Ràng buộc

1 ≤ n ≤ 3000, |a[i]| ≤ 10^9.

Ví dụ 1

Input

7
5 1 5 3 4 4 2

Output

5 4

Giải thích

Dữ liệu có các mức phân biệt 1,2,3,4,5. Giá trị cao nhất là 5; dù 5 xuất hiện hai lần, nó chỉ chiếm một mức. Mức lớn thứ hai phân biệt là 4, cũng xuất hiện hai lần nhưng vẫn chỉ tính một giá trị. Vì vậy output là 5 4.

Ví dụ 2

Input

4
9 9 9 9

Output

NO

Giải thích

Cả bốn phần tử đều bằng 9. Recursion xác lập max1=9 ở phần tử đầu, còn các phần tử sau đều trùng max1 nên không thể tạo max2 phân biệt. Khi duyệt hết mảng, has2 vẫn false, vì vậy chương trình phải in NO.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion, static arrays, top two distinct, reference state, duplicate handling
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100