聽說 std::sort() 很快。

但是，快還要更快！

現在給你一個長度為 $n$ 的陣列 $a$ ，你有辦法在 $o(n\log n)$ （嚴格小於 $n\log n$ ）的時間內找出 $a$ 的第 $k$ 大嗎？

本題為一道互動題。在這個問題中，你需要和評測系統進行互動。

一開始電腦會產生一個長度為 $n$ 的陣列 $a$ 及一個非負整數 $k$ ，並呼叫 int solve(int n, int a[], int k) ，你要實作這個函式，並使其回傳 $a$ 排序後的第 $k$ 項（從 $0$ 開始編號）。例如 $n=5,a=[3,1,4,1,5],k=2$ ，則需回傳 $3$ 。

你可以呼叫 int median(int b[], int m) 這個函式，其中 $m$ 為陣列 $b$ 的長度。他會回傳 $b$ 排序後的第 $\lfloor \frac{m}{2}\rfloor$ 項（從 $0$ 開始編號）。

實作細節

請在程式一開始引入標頭檔 lib0614.h。並實做下列函式，回傳陣列 $a$ 中第 $k$ 大的數字。

• int solve(int n, int a[], int k):
  • n：代表陣列長度。
  • a：陣列本身。
  • k：你要找的第 $k$ 大。