Largest Number

Problem Description

Cho một danh sách các số nguyên không âm (nums), sắp xếp chúng sao cho khi ghép lại thành một chuỗi, tạo ra số lớn nhất có thể.

Vì kết quả có thể rất lớn (vượt quá giới hạn của kiểu số nguyên), hãy trả về dưới dạng chuỗi.

Input Format

• Dòng 1: Số nguyên n — số lượng phần tử trong mảng
• Dòng 2: n số nguyên không âm nums[i]

Constraints

Output Format

Một chuỗi biểu diễn số lớn nhất có thể tạo ra từ việc ghép các số trong nums.

Examples

Input

2
11 2

Output

211

Explanation

Ta có "211" > "112", nên sắp xếp [2, 11] thành "211".

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

Maximum Subarray Sum

Bài toán

Cho một mảng số nguyên arr gồm n phần tử, hãy tìm tổng lớn nhất của một dãy con liên tiếp trong mảng.

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ử.
• Giải thuật cần có độ phức tạp tối ưu \(O(n)\) (sử dụng thuật toán Kadane).

Output Format

Trả về một số nguyên là tổng lớn nhất của một dãy con liên tiếp trong mảng.

Examples

Input 0

1 2 3 -2 5

Output 0

9

Input 1

-1 -2 -3 -4

Output 1

-1

Bài toán

Viết một hàm nhận vào một mảng số nguyên và trả về một mảng mới chứa các phần tử duy nhất theo đúng thứ tự xuất hiện trong mảng ban đầu.

Input Format

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

Constraints

• Có thể là mảng rỗng.
• Độ phức tạp tối ưu cần đạt là \(O(n)\).

Output Format

Trả về một mảng mới chứa các phần tử duy nhất theo thứ tự xuất hiện ban đầu.

Ví dụ

Input

1 2 3 1 2 4 5

Output

1 2 3 4 5

Input

5 5 5 5

Output

5