#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = (lookup_value & 15) + '0';
    number_buffer[length++] = (lookup_value >> 4) + '0';
  }
  if (number != 0 || length == 0) write_char(number + '0');
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
struct query {
  int a, b, index;
  bool operator<(const query &other) const { return a < other.a; }
};
int main() {
  IO::init();
  int N, Q;
  IO::read_int(N, Q);
  vector<int> H(N);
  for (int &h : H) IO::read_int(h);
  vector<query> queries(Q);
  for (int q = 0; q < Q; q++) {
    query &qry = queries[q];
    IO::read_int(qry.a, qry.b);
    qry.a--;
    qry.index = q;
  }
  sort(queries.begin(), queries.end());
  vector<int> including_count(Q, 1);
  vector<int> ending_length(N, 0);
  vector<int> best_ending;
  for (int i = 0, q = 0; i < N; i++) {
    auto it = lower_bound(best_ending.begin(), best_ending.end(), H[i]);
    ending_length[i] = it - best_ending.begin() + 1;
    while (q < Q && queries[q].a == i) {
      including_count[q] +=
          lower_bound(best_ending.begin(), best_ending.end(), queries[q].b) -
          best_ending.begin();
      q++;
    }
    if (it == best_ending.end())
      best_ending.push_back(H[i]);
    else
      *it = H[i];
  }
  int L = best_ending.size();
  best_ending.clear();
  vector<int> starting_length(N, 0);
  for (int i = N - 1, q = Q - 1; i >= 0; i--) {
    auto it = lower_bound(best_ending.begin(), best_ending.end(), H[i],
                          greater<int>());
    starting_length[i] = it - best_ending.begin() + 1;
    while (q >= 0 && queries[q].a == i) {
      including_count[q] += lower_bound(best_ending.begin(), best_ending.end(),
                                        queries[q].b, greater<int>()) -
                            best_ending.begin();
      q--;
    }
    if (it == best_ending.end())
      best_ending.push_back(H[i]);
    else
      *it = H[i];
  }
  vector<bool> part_of(N, false);
  vector<bool> necessary(N, false);
  vector<int> ending_freq(N + 1, 0);
  for (int i = 0; i < N; i++) {
    part_of[i] = ending_length[i] + starting_length[i] > L;
    if (part_of[i]) ending_freq[ending_length[i]]++;
  }
  for (int i = 0; i < N; i++)
    necessary[i] = part_of[i] && ending_freq[ending_length[i]] == 1;
  vector<int> answers(Q);
  for (int q = 0; q < Q; q++) {
    int base = necessary[queries[q].a] ? L - 1 : L;
    answers[queries[q].index] = max(including_count[q], base);
  }
  for (int q = 0; q < Q; q++) IO::write_int(answers[q], '\n');
}
