要能够组成三角形,需要满足任意两边之和大于第三边的条件。而如果一个连续子序列中任意三个数都满足这个条件,则需要该区间中最小的两个值的和大于最大值。该需求可以考虑使用双指针进行求解。
从1到i枚举右指针,并维护左指针。左指针的变化要求指针间所有数中,最小的两个值的和要大于指针间所有数中最大的值,因此在将第i个数加入时,动态移动左指针以满足要求。
有n根木棍排成一列,第i根木棍的长度为ai。
请你从中选出一个最长的子区间,使得区间内任意三根木棍都能构成三角形。只需要输出选出的区间端点即可。
第一行一个整数n(3≤n≤106),表示木棍的数量。
第二行n个整数,第i个整数ai(1≤a≤109)表示第i根木棍的长度。
输出一行两个整数,表示最长的满足条件的区间的两个端点,如果有多个满足条件的区间,输出左端点最小的区间。保证答案存在。
输入
3
1 2 3
输出
1 2
说明
选取2根木棍也满足“任意三根木棍均能构成三角形"。
输入
9
2 3 3 3 1 1 3 3 3
输出
1 4