4491. 二分查找

Easy输入输出数组二分查找

时间限制:2000 ms

内存限制:512 MiB

题面

给定 n(1n<216)n (1 \leq n < 2^{16}) 个元素组成的数组A (满足 A0...An1) A_0 \leq ... \leq A{n−1}), 以及一个需要查找的值 TT , 找出 TTA 中所有出现位置的序号区间(查找结果放置在一个变量的前半字(区间下限)和后半字(区间上限))。若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(1n<216)n (1 \leq n < 2^{16})

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

第3行:一个整数 TT

输出格式

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

样例

输入

5
1 2 2 3 4
2

输出

10002

输入

5
1 2 2 3 4
3

输出

30003

输入

5
1 2 2 3 4
13

输出

FFFFFFFF