Question
Optimizing Django Query

You are working on a Django application that stores a large dataset of user records. Each user record has an integer value representing the user's activity score. Your task is to optimize a query that finds the maximum score that is less than or equal to a given threshold T.

The scores are stored in a list arr of size n which is sorted in non-decreasing order. You need to find the maximum score x such that x <= T. If no such score exists, return -1.

Input

Line 1: KaTeX can only parse string typed expression — the number of user records.

Line 2: KaTeX can only parse string typed expression space-separated integers KaTeX can only parse string typed expression sorted in non-decreasing order, representing the activity scores.

Line 3: An integer KaTeX can only parse string typed expression — the threshold value.

Output

Print a single integer — the maximum score less than or equal to KaTeX can only parse string typed expression, or KaTeX can only parse string typed expression if no such score exists.

Example
Input
5

1 2 3 4 5
3
Output
3
Explanation
Given the scores KaTeX can only parse string typed expression and threshold KaTeX can only parse string typed expression, the maximum score less than or equal to KaTeX can only parse string typed expression is KaTeX can only parse string typed expression.

Online