No submission language available for this problem.

Background

Special for beginners, ^_^

Description

给定一个升序序列（元素可能会重复），要在这个序列中查找最后一个小于等于 $x$ 的元素的下标（下标从 $1$ 开始）。

题目保证：所有整数均在 $int$ 的表示范围内。

提示：此为二分查找的练习题，要用二分查找完成。

Format

Input

输入有 $3$ 行。第 $1$ 行输入 $n(0 < n \leq 100)$。

第 2 行输入 $n$ 个整数，即升序的序列。

第 3 行输入整数 $x$，即待查找的数。

Output

输出这个序列中最后一个小于等于 $x$ 的元素的下标（下标从 $1$ 开始），如果不存在输出 $-1$。

Samples

7
3 8 8 8 8 15 23
8

5

7
3 8 8 8 8 15 23
16

6

Limitation

1s, 1024KiB for each test case.