#include <cstdio>
My C++ program. It does not pass all test cases due to excessive time but it took 50 points. As far as the algorithm is concerned is right.
int main(){
	long long n = 0; long long m = 0;
	FILE* fin = stdin; //fopen("basket.txt", "rt");
	
	fscanf(fin, "%lld %lld", &n, &m);
	
	long long height[n+1]; height[0] = 0;
	long long total_sum[n+1]; total_sum[0] = 0;
	long long P[n+1]; P[0] = 0;
	
	for(long long i = 1; i < n+1; i++){
		fscanf(fin, "%lld", &height[i]);
		total_sum[i] = total_sum[i - 1] + height[i];
	}
	
	long long k = 100000000; long long subk; long long subk_i;
	long long i, j;
	long long l, r, x;
	bool flag1 = true; bool flag2 = true;
	long long power;
	
	for(long long a = 0; a < m; a++){
		fscanf(fin, "%lld %lld %lld\n", &l, &r, &x);
		flag1 = true; flag2 = true;
		k = 100000000;
		power = 0;
		i = l; j = l;
		long long max_power;
			flag2 = true;
			power = 0;
			subk = 0;
			subk_i = -1;
			while(j <= r && flag2){
				//printf("\t%lld\n", j);
				if(height[j] > k){
					i = j+1;
					j++;
					power = 0;
					subk = 0;
					subk_i = -1;
				}
				else{
					power += 2*(total_sum[j - 1] - total_sum[i - 1] + (j - i)*height[j]) + 2*height[j];
					if(height[j] >= subk){
						subk = height[j];
						subk_i = j;
					}
					if(power >= x){
						k = subk;
						power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
						i++;
						if(subk_i < i){
							subk = 0;
							for(int b = i; b <= j; b++){
								if(height[b] > subk){
									subk = height[b];
									subk_i = b;
								}
							}
						}
						if(i > j) j=i;
						else power -= 2*(total_sum[j - 1] - total_sum[i - 1] + (j - i)*height[j]) + 2*height[j];
					}
					else{
						j++;
					}
					if(j > r && power < x){
						flag1 = false;
						flag2 = false;
						j--;
					}
				}
			}
			power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
			i++;
			if(subk_i < i){
				subk = 0;
				for(int b = i; b <= j; b++){
					if(height[b] > subk){
						subk = height[b];
						subk_i = b;
					}
				}
			}
			while(i <= r){
				if(power >= x){
					k = subk;
				}
				else break;
				power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
				i++;
				if(subk_i < i){
					subk = 0;
					for(int b = i; b <= j; b++){
						if(height[b] > subk){
							subk = height[b];
							subk_i = b;
						}
					}
				}
			}
		
		if(k == 100000000) k = -1;
		printf("%lld\n", k);
	}
	
	return 0;
}