题目描述

输入一个已按从小到大排序的整数数组（无重复元素）和一个目标值，使用二分查找法判断目标值是否在数组中。若存在，输出其位置（从 1 开始计数）；若不存在，输出 Not found。

输入格式

第一行：整数 n（1 ≤ n ≤ 100）。第二行：n 个整数（有序数组，无重复元素）。第三行：整数 target（目标值）。

输出格式

一行，位置或 Not found。

样例

6
1 3 5 7 9 11
7

4

6
1 3 5 7 9 11
4

Not found

Limitation

1s, 1024KiB for each test case.