Cực đại của cực tiểu

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$ và một số nguyên $k$.

Bạn phải chia dãy thành đúng $k$ đoạn con liên tiếp, mỗi đoạn không rỗng. Nói cách khác, chọn các đoạn $[l_1,r_1],[l_2,r_2],\dots ,[l_k,r_k]$ thoả mãn $l_1=1$, $r_k=n$ và $l_i=r_{i-1}+1$ với mọi $i>1$.

Với mỗi đoạn, tính giá trị nhỏ nhất của các phần tử trong đoạn đó. Sau đó lấy giá trị lớn nhất trong $k$ giá trị nhỏ nhất vừa tính.

Hãy tìm giá trị lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: kích thước dãy và số đoạn phải chia.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất: giá trị lớn nhất có thể đạt được.

Ràng buộc

• $1\le k\le n\le {10}^5$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ