2022级统计计算机双学位《程序设计原理与C语言》上机作业

1034. 二分查找

单点时限: 2.0 sec

内存限制: 512 MB

给定 $n (1 \leq n < 2^{16}) $ 个元素组成的数组A (满足 $ A_0 \leq … \leq A{n−1})$, 以及一个需要查找的值 $T$ , 找出 $T$ 在 A 中所有出现位置的序号区间(查找结果放置在一个变量的前半字(区间下限)和后半字(区间上限))。若T没有在 A 中出现,查找结果表示为-1(即 0xFFFFFFFF)。

例如:

A包含1,2,2,3,4; T=2; 结果为 0x00010002

A包含1,2,2,3,4; T=3; 结果为 0x00030003

A包含1,2,2,3,4; T=13; 结果为 0xFFFFFFFF

输入格式

第1行:一个整数 $n (1 \leq n < 2^{16}) $ 。

第2行:按升序排列的 $n$ 个整数,整数之间有一个空格

第3行:一个整数 $T$

输出格式

十六进制 $(a-f用大写字母)$ 表示的序号区间

样例

Input
5
1 2 2 3 4
2
Output
10002
Input
5
1 2 2 3 4
3
Output
30003
Input
5
1 2 2 3 4
13
Output
FFFFFFFF