Second Largest Element

Bài toán

Viết một hàm để tìm phần tử lớn thứ hai trong một mảng số nguyên.
Nếu không có phần tử lớn thứ hai (tức là tất cả các phần tử bằng nhau hoặc mảng có ít hơn 2 phần tử), trả về None.

Input Format

Một mảng arr gồm n số nguyên (\(n \ge 1\)), với:

Constraints

• Mảng có ít nhất một phần tử.
• Phải có ít nhất hai giá trị khác nhau mới có thể tìm phần tử lớn thứ hai.
• Giải thuật tối ưu cần đạt độ phức tạp \(O(n)\).

Output Format

Trả về số nguyên là phần tử lớn thứ hai trong mảng hoặc None nếu không tồn tại.

Examples

Input 0

10 20 4 45 99

Output 0

45

Input 1

99 99 99

Output 1

None