#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vll vector<long long>
#define pr pair<int, int>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define mapi map<int,int>
#define mapll map<ll,ll>
#define all(x) x.begin(), x.end()
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
const int N = 2e5 + 5;
int seg[4 * N];
void update(int v, int l, int r, int L, int R, int val){
if(L > R)
return;
if(L == l && R == r){
seg[v] += val;
return;
}
int mid = (l + r) / 2;
update(2 * v + 1, l, mid, L, min(R, mid), val);
update(2 * v + 2, mid + 1, r, max(mid + 1, L), R, val);
}
int query(int v, int l, int r, int pos) {
if(l == r){
return seg[v];
}
int mid = (l + r) / 2;
if(pos <= mid){
return seg[v] + query(2 * v + 1, l, mid, pos);
}
else{
return seg[v] + query(2 * v + 2, mid + 1, r, pos);
}
}
void solve(){
int n, q;
cin>>n>>q;
int arr[n + 1];
for(int i = 0; i < n; i++) cin>>arr[i];
arr[n] = -1;
int l = 0;
vector<pair<pr, int>> v;
for(int i = 1; i <= n; i++){
if(arr[i] != arr[i - 1]){
v.push_back({{l, i - 1}, arr[i - 1]});
l = i;
}
}
v.push_back({{n, n}, INT_MAX});
vector<pair<pr, int>> order;
stack<pair<pr, int>> st;
order.push_back({{0, 0}, 0});
//monotonic stack precomputation
for(int i = 0; i < v.size(); i++){
int l = v[i].first.first;
int r = v[i].first.second;
int h = v[i].second;
if(st.empty()){
st.push({{l, r}, h});
continue;
}
if(st.top().second < h){
int curl = st.top().first.first;
int curr = st.top().first.second;
int curh = st.top().second;
st.pop(); i--;
if(st.empty()){
if(i == v.size() - 2) break;
order.push_back({{curl, curr}, (curr - curl + 1) * abs(h - curh)});
st.push({{curl, curr}, h});
continue;
}
int prevl = st.top().first.first;
int prevr = st.top().first.second;
int prevh = st.top().second;
int val = min(abs(curh - prevh), abs(curh - h));
order.push_back({{curl, curr}, (curr - curl + 1) * val});
if(abs(curh - prevh) <= abs(curh - h)){
st.pop();
st.push({{prevl, curr}, prevh});
}
else{
st.push({{curl, curr}, h});
}
}
else if(st.top().second == h){
int curl = st.top().first.first;
st.pop();
st.push({{curl, r}, h});
}
else{
st.push({{l, r}, h});
}
}
// prefix array of range updates
for(int i = 1; i < order.size(); i++) {
order[i].second += order[i - 1].second;
}
for(int i = 0; i <= 4 * n; i++) seg[i] = 0;
int answer[q]; int p = 1;
vector<pair<pr, int>> queries;
for(int i = 0; i < q; i++){
int time, pos;
cin>>time>>pos; pos--;
queries.push_back({{time, pos}, i});
}
// offline queries
sort(all(queries));
for(int i = 0; i < q; i++){
int time = queries[i].first.first;
int pos = queries[i].first.second;
int idx = queries[i].second, l, r;
while(p < order.size() && order[p].second <= time){
l = order[p].first.first;
r = order[p].first.second;
int val = (order[p].second - order[p - 1].second) / (r - l + 1);
update(0, 0, n - 1, l, r, val);
p++;
}
if(p == order.size()){
int d = time - order[p - 1].second;
d = d - (n - pos) + n;
answer[idx] = arr[pos] + query(0, 0, n - 1, pos) + d / n;
continue;
}
int d = time - order[p - 1].second;
l = order[p].first.first;
r = order[p].first.second;
d = d - (r - pos + 1) + (r - l + 1);
if(l <= pos && pos <= r){
//in the range
answer[idx] = arr[pos] + query(0, 0, n - 1, pos) + d / (r - l + 1);
}
else{
// outside the range
answer[idx] = arr[pos] + query(0, 0, n - 1, pos);
}
}
for(int i = 0; i < q; i++) cout<<answer[i]<<" ";cout<<endl;
}
signed main(){
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--){
solve();
}
return 0;
}
