1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;


int sum_waitings(int * array, int n, int d){
	
	int position = 0;
	int sum = 0;
	for(int i=0; i<n; i++){
		int val = array[i];
	
		if (val < (position + d)){
			sum += position + d - val;
			position += d;
		}
		else{
			position = val;
		}
	}
	return sum;
}

int compare(int * array, int n, int index, int diff){

	int sum_a = 0;
	int sum_b = 0;
	int sum_c = 0; 
	
	int position_a=0;
	int position_b=0;
	int position_c=0;
	
	int d_a = index;
	int d_b = index - 1;
	int d_c = index + 1;
	
	for(int i=0; i<n; i++){
		int val = array[i];
		
		// a
		position_a += d_a;
		if (val < position_a){
			sum_a += position_a - val;
		}
		else{
			position_a = val;
		}
		
		// b
		position_b += d_b;
		if (val < position_b){
			sum_b += position_b - val;
		}
		else{
			position_b = val;
		}
		
		// c
		position_c += d_c;
		if (val < position_c){
			sum_c += position_c - val;
		}
		else{
			position_c = val;
		}
	}
	
	if ( (sum_c - sum_a) == diff && (sum_a - sum_b) != diff){
		return sum_a; // success
	}
	else if( (sum_c - sum_a) == diff && (sum_a - sum_b) == diff){
		return 0; // the same difference - go down
	}
	else{
		return -1; // go up
	}
}

int main() {
	int n, m;
	int max = 1000000;
	
	scanf("%d %d", &n, &m);
	
	int constans = 0;
	
	for(int i=1; i<=n; i++){
		constans += i;
	}
	
	int * clients = new int[n];
	
	// read t moments
	getchar();
	for (int i=0; i<n; i++){
		char c = '0';
		int c_number = 0;
		int x = 0;
		do{
			c_number = (int)c - 48;
			x = x*10 + c_number;
			c = getchar();
		}while(c >= 48 && c < 58);
		//cout << "znalazlem: " << x << "\n";
		
		clients[i] = x;
	}
	
	// binary search
	
	bool condition = false;
	
	int index = max / 2;
	int old_index = index;
	
	int result;
	while (!condition){
		if(old_index != 1){
			old_index /= 2;
		}
		result = compare(clients, n, index, constans);
		if (result > 0){
			condition = true;
			break;
		}
		else if(result == 0){
			// go down
			index -= old_index;
		}
		else{
			// go up
			index += old_index;
		}
	}

	
	// read d moments
	for (int i=0; i<m; i++){
		char c = '0';
		int c_number = 0;
		int x = 0;
		do{
			c_number = (int)c - 48;
			x = x*10 + c_number;
			c = getchar();
		}while(c >= 48 && c < 58);
		//cout << "znalazlem: " << x << "\n";
		if(x >= index){
			cout << result + constans * (x - index) << "\n";
		}
		else{
			cout << sum_waitings(clients, n, x) << "\n";
		}
	}	
	
	delete[] clients;
  
  return 0;
}