题意

n个点1~n，i到i+1的距离为a[i]，现在可以在两个点之间建一个传送门，则两点之间距离为0，求建传送门后1号出发的最远距离最小是多少？

题解

a[i]的前缀和为s[i]。

假设在A、B两点建立传送门后，两点距离为dis[i][j]。

对于B固定的情况，最远距离要么是s[n-1]-s[B]，要么是dis[1][k]里的最大值，k为A、B两点之间的点， dis[1][k]=min(s[k],s[A]+(s[B]-s[k]))。s[A]显然越小越好。所以就让A在第一个点的位置。于是dis[1][k]=min(s[k],s[B]-s[k])。

假设最大的dis[1][k]的 k 为 C。

满足\[s[j]<s[B]-s[j]且s[j+1]\ge s[B]-s[j+1]\]的 j 或者 j+1 就是 C（其实就是AB中间位置两边的点）。

这里的C是随着B递增不会减小的，因此不用O（\(n^2\)），只要每次维护 j 满足不等式即可。

代码

#include
    
     #include
     
      using namespace std;int n;long long s[100005];//注意要开long longint main(){    int t;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        for(int i=1;i