#include <bits/stdc++.h> using namespace std; const int MAXN=100008; int n,blocksize,k,lastnum; int arr[MAXN], brr[MAXN], tag[330]; int group[330][330]; int fr(); void Reset(int t) { int l=(t-1)*blocksize+1; //第 t 块的区间[l,r] int r=t*blocksize; if (t==k) r=n; for (int i=l,j=0; i<=r; i++) group[t][j++] = arr[i] ; // 更新 group[t] // 重新排序 if ( t==k ) // t为最后1块 sort( group[t], group[t]+lastnum); else sort( group[t], group[t]+blocksize); } void Update(int l, int r, int c) { int R=min(r, brr[l]*blocksize ); //更新 l 所在不完整块的数据 for (int i=l; i<=R; i++) arr[i]+= c; Reset( brr[l] ); // 更新块 brr[l] if ( brr[l] != brr[r] ) // l, r 不在同一块 { int L=( brr[r]-1)*blocksize+1; for (int i=L; i<=r; i++) //更新 r 所在不完整块的数据 arr[i]+=c; Reset( brr[r] ); // 更新块 brr[r] } for (int i=brr[l]+1; i<=brr[r]-1; i++) //添加懒惰标签( l, r 跨越的完整块 ) tag[i]+=c; } int Find(int l, int r, int c) { int xmax=-1; int R=min(r, brr[l]*blocksize ); for (int i=l; i<=R; i++) //比较 l 所在不完整块的数据 { int x=arr[i]+tag[ brr[l] ]; if ( x< c && x>xmax ) xmax=x; } if ( brr[l] != brr[r] ) // l, r 不在同一块 { int L= (brr[r]-1)*blocksize +1 ; for (int i=L; i<=r; i++) //比较 r所在不完整块的数据 { int x=arr[i]+tag[ brr[r] ]; if ( x< c && x>xmax ) xmax=x; } } for (int i=brr[l]+1; i<=brr[r]-1; i++) //二分查找( l, r 跨越的完整块 ) { int j= lower_bound( group[i], group[i]+blocksize, c-tag[i] ) - group[i]; if (j==0) continue; // 所有数都>=c int x=group[i][--j]+tag[i]; if ( x > xmax ) xmax=x; } return xmax; } int main() { // freopen("array1.in","r",stdin); // freopen("array1.out","w",stdout); n=fr(); blocksize=sqrt(n); lastnum=n%blocksize; // 最后1组分块的大小; if ( lastnum==0 ) lastnum=blocksize; k=1; for (int i=1,j=0; i<=n; i++) // 分块, 共有 k= n/blocksize 块; { arr[i]=fr(); if( j==blocksize ) k++,j=0; // 块序号k brr[i]=k; // brr[i]记录 i 属于第 k块 group[k][j++]= arr[i] ; // 分入 group[k] } for (int i=1; i<k; i++) // 对块排序 sort( group[i], group[i]+blocksize); sort( group[k], group[k]+lastnum); // 对最后1块排序 for (int i=1; i<=n; i++) { int cmd=fr(), l=fr(), r=fr(), c=fr(); if ( cmd==0 ) Update(l, r, c); // 更新数据 else { int ans=Find(l, r, c); printf("%d\n",ans); } } return 0; } int fr(){ int x=0,flag=1; char ch=getchar(); while( ch<'0'||ch>'9' ) { if( ch=='-') flag=-1; ch=getchar(); } while( ch>='0'&& ch<='9' ) { x= x*10 + ch- '0'; ch=getchar(); } return x*flag; }