#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int MAX_N = 1e5 + 47;

bool good[MAX_N];

vector<int> scanline[MAX_N];

int status;

int n, m, a[MAX_N];

tuple<int, int> q[MAX_N];

void zip_zip()
{
  vector<int> kek;
  for (int i = 1; i <= n; i++)
  {
    kek.push_back(a[i]);
  }
  for (int i = 1; i <= m; i++)
  {
    auto [pos, val] = q[i];
    kek.push_back(val);
  }
  sort(kek.begin(), kek.end());
  kek.resize(unique(kek.begin(), kek.end()) - kek.begin());
  for (int i = 1; i <= n; i++)
  {
    a[i] = lower_bound(kek.begin(), kek.end(), a[i]) - kek.begin() + 1;
  }
  for (int i = 1; i <= m; i++)
  {
    auto &[pos, val] = q[i];
    val = lower_bound(kek.begin(), kek.end(), val) - kek.begin() + 1;
  }
}

struct node
{
  node *l, *r;
  int val;
  node()
  {
    l = r = nullptr;
    val = 0;
  }
  node(int x)
  {
    l = r = nullptr;
    val = x;
  }
  node(node *lf, node *rg)
  {
    l = lf;
    r = rg;
    val = max(l->val, r->val);
  }
};

node *build(int tl, int tr)
{
  if (tl == tr)
  {
    return new node();
  }
  else
  {
    int tm = (tl + tr) >> 1;
    return new node(build(tl, tm), build(tm + 1, tr));
  }
}

node *update(node *v, int tl, int tr, int pos, int val)
{
  if (tl == tr)
  {
    val = max(val, v->val);
    return new node(val);
  }
  else
  {
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
    {
      return new node(update(v->l, tl, tm, pos, val), v->r);
    }
    else
    {
      return new node(v->l, update(v->r, tm + 1, tr, pos, val));
    }
  }
}

int get_mx(node *v, int tl, int tr, int l, int r)
{
  if (tl > r || tr < l)
  {
    return 0;
  }
  if (tl >= l && tr <= r)
  {
    return v->val;
  }
  int tm = (tl + tr) >> 1;
  return max(get_mx(v->l, tl, tm, l, r), get_mx(v->r, tm + 1, tr, l, r));
}

int dp1[MAX_N], dp2[MAX_N], base_mx;

void build_good()
{
  for (int i = 1; i <= n; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      if (a[i] < a[j] && dp1[i] + dp2[j] == base_mx)
      {
        scanline[i + 1].push_back(1);
        scanline[j].push_back(-1);
      }
    }
  }
  for (int i = 1; i <= n; i++)
  {
    for (auto x : scanline[i])
    {
      status += x;
    }
    if (status != 0)
    {
      good[i] = 1;
    }
  }
}

const int MAX_V = 8e4;

signed main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef _47
    freopen("4.cpp", "r", stdin), freopen("7.cpp", "w", stdout);
  #endif
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++)
  {
    int pos, val;
    cin >> pos >> val;
    q[i] = {pos, val};
  }
  node *p[n + 1], *s[n + 2];
  p[0] = build(1, MAX_V);
  s[n + 1] = build(1, MAX_V);
  for (int i = 1; i <= n; i++)
  {
    int new_val = get_mx(p[i - 1], 1, MAX_V, 1, a[i] - 1) + 1;
    dp1[i] = new_val;
    p[i] = update(p[i - 1], 1, MAX_V, a[i], new_val);
  }
  for (int i = n; i >= 1; i--)
  {
    int new_val = get_mx(s[i + 1], 1, MAX_V, a[i] + 1, MAX_V) + 1;
    dp2[i] = new_val;
    s[i] = update(s[i + 1], 1, MAX_V, a[i], new_val);
  }
  base_mx = get_mx(p[n], 1, MAX_V, 1, MAX_V);
  build_good();
  for (int i = 1; i <= m; i++)
  {
    auto [pos, val] = q[i];
    int ans = base_mx - 1;
    if (good[pos])
    {
      ans = max(ans, base_mx);
    }
    ans = max(ans, get_mx(p[pos - 1], 1, MAX_V, 1, val - 1) + get_mx(s[pos + 1], 1, MAX_V, val + 1, MAX_V) + 1);
    cout << ans << '\n';
  }
  return 0;
}