K-th Highest Score Selection

Given a list of unsorted student scores and an integer k, select the k-th highest score. If there are multiple students with the same score, the student appearing earlier in the list is given priority. Formally, let \( S = [s_1, s_2, \dots, s_n] \) be the list of scores. After sorting the scores in descending order (with ties broken by original order), the answer is the element at position \( k \) (1-indexed). If \( k n \), output "Invalid input".

inputFormat

The input is read from standard input (stdin) and consists of three lines:

• The first line contains a single integer \( n \), the number of scores.
• The second line contains \( n \) space-separated integers representing the scores.
• The third line contains the integer \( k \), indicating that the k-th highest score will be selected.

outputFormat

Output a single line to standard output (stdout):

• If the input is valid, output the k-th highest score.
• If \( k \) is invalid (i.e. \( k n \)), output "Invalid input".

## sample

6
50 80 90 70 90 60
3

80

</p>