Smallest bundle that is large enough

Problem

A shop sells bundles of different sizes, listed in ascending order. A customer needs at least x units. Print the size of the smallest bundle that has at least x units, or -1 if none does.

Input, output and limits

Input: Line 1: n. Line 2: n bundle sizes in ascending order. Line 3: the need x.
Output: One integer: the bundle size, or -1.
Constraints: 1 ≤ n ≤ 10^5
1 ≤ size, x ≤ 10^9

Examples

Example

Input

5
10 25 50 100 250
60

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

This is a lower bound: the first bundle whose size is at least x.

Hint 2

If the lower bound is n, no bundle is large enough.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

First and last position of a leveleasy
Orders inside a price rangeeasy
Integer square rooteasy
Smallest value in a rotated listmedium
Count one stock leveleasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems