You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目概述

给你一个按照非递减顺序排列的整数数组 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$