Tóm tắt đề bài: Nhập vào ~n~ (~1 \le n \le 10^7~) số nguyên dương. Hãy in ra số lớn thứ ~3~ trong mảng.

Subtask 1: ~n \le 10^5~.

Sắp xếp lại mảng và in ra phần tử thứ ~3~.

Độ phức tạp: ~O~ (~n \times \log n~).

Subtask 2: ~n \le 10^7~.

Duy trì ba biến ~a~, ~b~, ~c~ tương ứng phần tử lớn nhất, lớn nhì và lớn ba. Ban đầu, cả ba số đều bằng ~0~.

Nhập liên tục vào ~n~ số ~x~, xét các trường hợp sau:

• Nếu ~x \ge a~, ta thấy: số lớn nhất sẽ trở thành số thứ hai, số lớn thứ hai trở thành số lớn thứ ba. Vì vậy, ~c = b~, ~b = a~, và ~a = x~.
• Nếu ~x \ge b~, tương tự như trên, ta sẽ có ~c = b~, ~b = x~.
• Nếu ~x \ge c~, ta sẽ có ~c = x~.
• Cuối cùng, ta bỏ qua số ~x~ vì số ~x~ sẽ không đóng góp vào kết quả.

Cuối cùng, ta in ra ~c~, hay số lớn thứ ba.

Độ phức tạp: ~O~ (~n~).

Cách này có thể AC với time limit 2 giây. Để tối ưu hơn nữa, có thể sử dụng fast input, tuy nhiên điều này là không tưởng trong một kỳ thi offline.