Chia đoạn

Trong một ngôi làng nọ, người dân tổ chức một cuộc thi thường niên để tìm ra "Bậc Thầy Phân Chia". Cuộc thi này xoay quanh một dãy số cổ xưa \(A\) được truyền qua nhiều thế hệ. Luật chơi như sau:

• Người chơi sẽ chọn một khoảng giá trị \([X, Y]\) sao cho \(X \leq Y\).
• Sau đó, họ phải chia dãy \(A\) thành \(K\) \((K \leq N)\) đoạn con liên tiếp.

Mỗi đoạn con phải thỏa mãn:

• Tất cả các phần tử của dãy \(A\) đều nằm chính xác trong một đoạn con.
• Trong mỗi đoạn con, số lượng phần tử nằm trong khoảng \([X, Y]\) phải lớn hơn số lượng phần tử nằm ngoài khoảng này.

Điểm của một cách chọn được tính bằng \(Y - X\). Điểm càng thấp thì thứ hạng càng cao.
Nếu hai người chơi có cùng điểm, người chọn giá trị \(X\) nhỏ hơn sẽ xếp hạng cao hơn.

Bây giờ, hãy giúp một người chơi đặc biệt, Eldric - chàng trai trẻ đầy tham vọng nhưng chưa đủ kinh nghiệm, để anh ấy chắc chắn giành được vị trí đầu bảng.

Yêu cầu: Hãy tìm cách chọn khoảng giá trị \([X, Y]\) sao cho tồn tại cách chia dãy \(A\) thành \(K\) đoạn con liên tiếp để đạt thứ hạng cao nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \leq K \leq N \leq 2 \times 10^5)\), lần lượt là số phần tử trong dãy \(A\) và số đoạn con cần chia.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq N)\), biểu diễn các phần tử của dãy \(A\).
• Các số trong một dòng được ngăn cách bởi dấu cách.

Output

Một dòng chứa hai số \(X, Y\) tìm được.

Example

2 1
1 2

1 2

4 2
1 2 2 2

2 2

11 3
5 5 5 1 5 5 1 5 5 5 1

5 5

Scoring

• Có \(20\%\) số điểm ứng với \(1 \leq N \leq 15\).
• Có \(30\%\) số điểm ứng với \(15 < N \leq 1000\).
• Có \(50\%\) số điểm ứng với \(1000 < N \leq 2 \times 10^5\).