挺牛题，没做出来，但是参考了 Rainbow 博客之后发现这些套路自己其实都会啊 QwQ。
我提交的翻译：
给定一个长度为 \(n\) 的数组 \(x\)，接下来你有 \(q\) 次询问。
第 \(i\) 次询问给出一个区间 \(l,r\)，设 \(k=r-l+1\)，你提取出 \(x\) 数组下标在 \(l,r\) 之间的区间 \(y_i=x_{i+l}(0\le i<k)\)。
考虑 \(k\) 个点 \((0,y_0),(1,y_1)\dots(k-1,y_{k-1})\)。你需要找到一条直线的三个参数 \(a,b,c\)，满足 \(\forall 0\le i<k,y_i=\lfloor \frac{ai+b}{c}\rfloor\)。若有多条这样的直线，输出 \((c,a,b)\) 三元组字典序最小的一个。
保证对于整个数组，即 \(l=1,r=n\) 的询问一定存在一组合法的解。
\(n,q\le 10^5\)，多组询问。
突破口在于考虑固定直线的斜率 \(K\)，那么截距 \(B\) 就需要满足不等式 \(\max(a_i-Ki)\le B < \min (a_i-Ki) +1\)。当 \(a_i-Ki\) 数组的极差要严格小于 \(1\) 时，取 \(B=\max(a_i-Ki)\) 就是字典序最小的解了。
接下来考虑什么样的 \(K\) 能让极差小于 \(1\)。一个很牛的想法是注意到在 \(K\) 增大的时候，最小值的位置总是在往右边移动，最大值的位置总是往左边移动；而当我们想要减小极差时，如果最小值在最大值左边，那么只有增大 \(K\) 才能减小这个极差。这说明这个 \(K\) 是有可二分性的，在 Stern-Brocot 树上二分即可。
见过无数次经典的技巧，SBT 二分需要倍增优化跳直链。这里我们并不好确定倍增的上界，不过虽然我不会证，既然它要我们输出答案，那么猜测这个答案一定是在 long long 范围内的。直接用倍增试探答案的最高二进制位。
现在考虑询问区间 \(a_i-Ki\) 的极值，这是区间凸包问题。不过我们不能带很多 \(\log\)，所以不能直接上线段树做 \(O(n\log n)-O(m\log^2 n)\) 的做法。
考虑用回滚莫队维护凸包，由于斜率已经有序所以直接正常拿栈维护，这样询问就只有一个 \(\log\) 了。
当然另一个 polylog 做法 rainbow 也提了，就是类似猫树一样优化那个线段树的区间凸包做法，目测比回滚莫队难写很多，不管这个做法了。
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef pair<ll,ll> pll;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
const int P=998244353;
int n,q,sq;
int a[N];
int ql[N],qr[N];
inline int bel(int x){return (x-1)/sq+1;}
struct MinHull{
int stk[N],tp;
bool check(int x,int y,int z){
return (ll)(a[z]-a[y])*(z-x)<=(ll)(a[z]-a[x])*(z-y);
}
void append(int i){
while(tp>1&&check(stk[tp-1],stk[tp],i)) --tp;
stk[++tp]=i;
}
int query(ll x,ll y){
int l=1,r=tp;
while(l<r){
int o=(l+r)>>1;
if((lll)x*(stk[o+1]-stk[o])<(lll)y*(a[stk[o+1]]-a[stk[o]])) r=o;
else l=o+1;
}
return stk[l];
}
}Mn1,Mn2;
struct MaxHull{
int stk[N],tp;
bool check(int x,int y,int z){
return (ll)(a[z]-a[y])*(z-x)>=(ll)(a[z]-a[x])*(z-y);
}
void append(int i){
if(tp&&a[i]<=a[stk[tp]]) return;
while(tp>1&&check(stk[tp-1],stk[tp],i)) --tp;
stk[++tp]=i;
}
int query(ll x,ll y){
int l=1,r=tp;
while(l<r){
int o=(l+r)>>1;
if((lll)x*(stk[o+1]-stk[o])>(lll)y*(a[stk[o+1]]-a[stk[o]])) r=o;
else l=o+1;
}
return stk[r];
}
}Mx1,Mx2;
int qmn(ll x,ll y){
int ps=Mn1.query(x,y);
if(Mn2.tp){
int nps=Mn2.query(x,y);
if((lll)y*a[nps]-(lll)x*nps<(lll)y*a[ps]-(lll)x*ps) ps=nps;
}
return ps;
}
int qmx(ll x,ll y){
int ps=Mx1.query(x,y);
if(Mx2.tp){
int nps=Mx2.query(x,y);
if((lll)y*a[nps]-(lll)x*nps>(lll)y*a[ps]-(lll)x*ps) ps=nps;
}
return ps;
}
int dir(ll x,ll y){
int pmn=qmn(x,y);lll vmn=(lll)y*a[pmn]-(lll)x*pmn;
int pmx=qmx(x,y);lll vmx=(lll)y*a[pmx]-(lll)x*pmx;
if(vmx-vmn>=y){
if(pmn>pmx) return -1;
if(pmn<pmx) return 1;
}
return 0;
}
pll sol(ll a,ll b,ll c,ll d){
int w=dir(a+b,c+d);
if(w<0){
int t=0;
while(dir((a<<(t+1))+b,(c<<(t+1))+d)==w) ++t;
b+=(a<<t);d+=(c<<t);
while(t){--t;if(dir((a<<t)+b,(c<<t)+d)==w) b+=(a<<t),d+=(c<<t);}
return sol(a,b,c,d);
}
if(w>0){
int t=0;
while(dir((b<<(t+1))+a,(d<<(t+1))+c)==w) ++t;
a+=(b<<t);c+=(d<<t);
while(t){--t;if(dir((b<<t)+a,(d<<t)+c)==w) a+=(b<<t),c+=(d<<t);}
return sol(a,b,c,d);
}
return pll(a+b,c+d);
}
ll qa[N],qb[N],qc[N];
int ss[N];
void proc(int i){
auto [x,y]=sol(0,1,1,0);
int ps=qmx(x,y);
qa[i]=x;qb[i]=(lll)y*a[ps]-(lll)x*(ps-ql[i]);qc[i]=y;
}
void build(int l,int r){
Mn1.tp=Mx1.tp=0;
for(int i=l;i<=r;++i) Mn1.append(i);
for(int i=l;i<=r;++i) Mx1.append(i);
}
vector<int> vec[N];
void solve(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=2;i<=n;++i) ss[i]=ss[i-1]+(a[i-1]!=a[i]);
sq=ceil(sqrt(n));
q=read();
for(int i=1;i<=q;++i){
ql[i]=read(),qr[i]=read();
if(ss[ql[i]]==ss[qr[i]]){qa[i]=0;qb[i]=a[ql[i]];qc[i]=1;continue;}
int bl=bel(ql[i]),br=bel(qr[i]);
if(bl<br) vec[bl].emplace_back(i);
else Mn2.tp=Mx2.tp=0,build(ql[i],qr[i]),proc(i);
}
for(int x=1;x<bel(n);++x){
sort(vec[x].begin(),vec[x].end(),[](int a,int b){return qr[a]<qr[b];});
Mn2.tp=Mx2.tp=0;
int ps=x*sq+1;
for(int t:vec[x]){
build(ql[t],x*sq);
while(ps<=qr[t]) Mn2.append(ps),Mx2.append(ps),++ps;
proc(t);
}
vec[x].clear();
}
for(int i=1;i<=q;++i) printf("%lld %lld %lld\n",qa[i],qb[i],qc[i]);
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}