题目概述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

本题有多组测试数据。

如果数组中不存在目标值 target，返回 -1 -1。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

格式

输入格式

以文件结束符（EOF）为程序结束标志。

对于每组数据：

第一行，一个整数 $n$，代表 nums 的元素个数。

接下来一行有 $n$ 个整数，第 $i$ 个数字代表 nums 的第 $i$ 个元素，每个数字以空格隔开。

最后一行，一个整数 $target$ ，代表目标值

输出格式

对于每组数据：输出一行，两个整数，代表查找的结果。

样例

6
5 7 7 8 8 10
8

3 4

6
5 7 7 8 8 10
6
5
1 2 3 5 5
5

-1 -1
3 4

0
0

-1 -1

提示：

令 $q$ 为数据组数

$1 \leq$ $q$ $\leq 10^3$

$0 \leq$ nums.length $\leq 10^6$

$-10^9 \leq$ nums[i] $\leq 10^9$

nums 是一个非递减数组

$-10^9 \leq$ target $\leq 10^9$