Vasya has decided to build a zip-line on trees of a nearby forest. He wants the line to be as long as possible but he doesn't remember exactly the heights of all trees in the forest. He is sure that he remembers correct heights of all trees except, possibly, one of them.

It is known that the forest consists of n trees staying in a row numbered from left to right with integers from 1 to n. According to Vasya, the height of the i-th tree is equal to hi. The zip-line of length k should hang over k (1 ≤ k ≤ n) trees i1, i2, ..., ik (i1 < i2 < ... < ik) such that their heights form an increasing sequence, that is hi1 < hi2 < ... < hik.

Petya had been in this forest together with Vasya, and he now has q assumptions about the mistake in Vasya's sequence h. His i-th assumption consists of two integers ai and bi indicating that, according to Petya, the height of the tree numbered ai is actually equal to bi. Note that Petya's assumptions are independent from each other.

Your task is to find the maximum length of a zip-line that can be built over the trees under each of the q assumptions.

In this problem the length of a zip line is considered equal to the number of trees that form this zip-line.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 400 000) — the number of the trees in the forest and the number of Petya's assumptions, respectively.

The following line contains n integers hi (1 ≤ hi ≤ 109) — the heights of trees according to Vasya.

Each of the following m lines contains two integers ai and bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 109).

Output

For each of the Petya's assumptions output one integer, indicating the maximum length of a zip-line that can be built under this assumption.

Examples

Input

4 4
1 2 3 4
1 1
1 4
4 3
4 5


Output

4
3
3
4


Input

4 2
1 3 2 6
3 5
2 4


Output

4
3

Note

Consider the first sample. The first assumption actually coincides with the height remembered by Vasya. In the second assumption the heights of the trees are (4, 2, 3, 4), in the third one they are (1, 2, 3, 3) and in the fourth one they are (1, 2, 3, 5).
import java.io.*;
import java.util.*;

public class D {

	class Event {
		int pos;
		int was;
		int now;

		public Event(int pos, int was, int now) {
			super();
			this.pos = pos;
			this.was = was;
			this.now = now;
		}

		@Override
		public String toString() {
			return "Event [pos=" + pos + ", was=" + was + ", now=" + now + "]";
		}

	}

	class SegmentTreeMax {
		int[] max;

		public SegmentTreeMax(int n) {
			max = new int[n * 4];
		}

		int get(int v, int l, int r, int needL, int needR) {
			if (needL > needR) {
				return 0;
			}
			if (l == needL && r == needR) {
				return max[v];
			}
			int m = (l + r) >> 1;
			return Math.max(get(v * 2 + 1, l, m, needL, Math.min(needR, m)),
					get(v * 2 + 2, m + 1, r, Math.max(needL, m + 1), needR));
		}

		void upd(int v, int l, int r, int need, int val) {
			if (l == r) {
				max[v] = Math.max(max[v], val);
			} else {
				int m = (l + r) >> 1;
				if (m >= need) {
					upd(v * 2 + 1, l, m, need, val);
				} else {
					upd(v * 2 + 2, m + 1, r, need, val);
				}
				max[v] = Math.max(max[v * 2 + 1], max[v * 2 + 2]);
			}
		}
	}

	class CoolSegmentTree {
		int[][] max;
		int[] ans;

		public CoolSegmentTree(int n, int[] max2) {
			max = new int[2][n * 4];
			ans = new int[n * 4];
			max[1] = max2;
			build(0, 0, n - 1);
		}

		void build(int v, int l, int r) {
			if (l == r) {
				ans[v] = max[1][v];
			} else {
				int m = (l + r) >> 1;
				build(v * 2 + 1, l, m);
				build(v * 2 + 2, m + 1, r);
				calc(v);
			}
		}

		int[] getAll(int id, int max) {
			int[] res = new int[max];
			get(id, 0, 0, max - 1, res);
			return res;
		}

		void get(int id, int v, int l, int r, int[] res) {
			if (l == r) {
				res[l] = max[id][v];
			} else {
				int m = (l + r) >> 1;
				get(id, v * 2 + 1, l, m, res);
				get(id, v * 2 + 2, m + 1, r, res);
			}
		}

		int get(int id, int v, int l, int r, int needL, int needR) {
			if (needL > needR) {
				return 0;
			}
			if (l == needL && r == needR) {
				return max[id][v];
			}
			int m = (l + r) >> 1;
			return Math
					.max(get(id, v * 2 + 1, l, m, needL, Math.min(needR, m)),
							get(id, v * 2 + 2, m + 1, r,
									Math.max(needL, m + 1), needR));
		}

		void upd(int id, int v, int l, int r, int need, int val) {
			if (l == r) {
				max[id][v] = val;
				ans[v] = Math.max(max[0][v], max[1][v]);
			} else {
				int m = (l + r) >> 1;
				if (m >= need) {
					upd(id, v * 2 + 1, l, m, need, val);
				} else {
					upd(id, v * 2 + 2, m + 1, r, need, val);
				}
				max[id][v] = Math.max(max[id][v * 2 + 1], max[id][v * 2 + 2]);
				calc(v);
			}
		}

		void calc(int v) {
			ans[v] = Math.max(ans[v * 2 + 1], ans[v * 2 + 2]);
			ans[v] = Math.max(ans[v], max[0][v * 2 + 1] + max[1][v * 2 + 2]);
		}

	}

	int[] solve(int[] h, int[] a, int[] b) {
		int n = h.length;
		int m = a.length;
		int[] res = new int[a.length];
		ArrayList<Integer> all = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			all.add(h[i]);
		}
		for (int i = 0; i < m; i++) {
			all.add(b[i]);
		}
		Collections.sort(all);
		ArrayList<Integer> all2 = new ArrayList<>();
		for (int x : all) {
			if (all2.size() > 0 && all2.get(all2.size() - 1) - x == 0) {
				continue;
			}
			all2.add(x);
		}
		for (int i = 0; i < n; i++) {
			h[i] = Collections.binarySearch(all2, h[i]);
		}
		for (int i = 0; i < m; i++) {
			b[i] = Collections.binarySearch(all2, b[i]);
		}
		int max = all2.size();
		SegmentTreeMax st = new SegmentTreeMax(max);
		Event[] events = new Event[n];
		int[] real = new int[max];
		for (int i = n - 1; i >= 0; i--) {
			int curMax = st.get(0, 0, max - 1, h[i] + 1, max - 1);
			if (real[h[i]] < curMax + 1) {
				int was = real[h[i]];
				real[h[i]] = curMax + 1;
				st.upd(0, 0, max - 1, h[i], real[h[i]]);
				events[i] = new Event(h[i], was, real[h[i]]);
			}
		}
		ArrayList<Ask>[] ask = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			ask[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			ask[a[i]].add(new Ask(a[i], b[i], i));
		}
		Arrays.fill(real, 0);
		CoolSegmentTree coolST = new CoolSegmentTree(max, st.max);
		for (int i = 0; i < n; i++) {
			if (events[i] != null) {
				coolST.upd(1, 0, 0, max - 1, events[i].pos, events[i].was);
			}
			// System.err.println(Arrays.toString(coolST.getAll(0, max)));
			// System.err.println(Arrays.toString(coolST.getAll(1, max)));
			int nowAnswer = coolST.ans[0];
			for (Ask as : ask[i]) {
				res[as.id] = nowAnswer;
				int left = coolST.get(0, 0, 0, max - 1, 0, as.value - 1);
				int right = coolST.get(1, 0, 0, max - 1, as.value + 1, max - 1);
				res[as.id] = Math.max(res[as.id], left + 1 + right);
			}
			int curMax = coolST.get(0, 0, 0, max - 1, 0, h[i] - 1);
			if (real[h[i]] < curMax + 1) {
				real[h[i]] = curMax + 1;
				coolST.upd(0, 0, 0, max - 1, h[i], real[h[i]]);
			}
		}
		return res;
	}

	class Ask {
		int pos;
		int value;
		int id;

		public Ask(int pos, int value, int id) {
			super();
			this.pos = pos;
			this.value = value;
			this.id = id;
		}

	}

	int get(int[] a) {
		int[] res = new int[a.length + 2];
		Arrays.fill(res, Integer.MAX_VALUE);
		res[0] = -1;
		for (int i = 0; i < a.length; i++) {
			int left = 0, right = a.length;
			while (right - left > 1) {
				int mid = (left + right) >> 1;
				if (res[mid] >= a[i]) {
					right = mid;
				} else {
					left = mid;
				}
			}
			if (res[left] < a[i] && res[right] > a[i]) {
				res[right] = a[i];
			}
		}
		int result = 0;
		while (res[result] != Integer.MAX_VALUE) {
			result++;
		}
		return result - 1;
	}

	int[] stupid(int[] h, int[] a, int[] b) {
		int[] res = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			int now = h[a[i]];
			h[a[i]] = b[i];
			res[i] = get(h);
			h[a[i]] = now;
		}
		return res;
	}

	public void solve123() {
		Random rnd = new Random(123);
		final int M = 400000;
		for (int it = 0; it < 123123; it++) {
			System.err.println("it = " + it);
			int n = 1 + rnd.nextInt(M);
			int m = 1 + rnd.nextInt(M);
			int[] h = new int[n];
			for (int i = 0; i < n; i++) {
				h[i] = rnd.nextInt(M);
			}
			int[] a = new int[m];
			int[] b = new int[m];
			for (int i = 0; i < m; i++) {
				a[i] = rnd.nextInt(n);
				b[i] = rnd.nextInt(M);
			}
			if (it == 63) {
				System.err.println("!!");
			}
			long START = System.currentTimeMillis();
			int[] my = solve(h, a, b);
			System.err.println(System.currentTimeMillis() - START);
			// int[] corr = stupid(h, a, b);
			// for (int i = 0; i < my.length; i++) {
			// if (my[i] != corr[i]) {
			// System.err.println(Arrays.toString(h));
			// System.err.println(Arrays.toString(a));
			// System.err.println(Arrays.toString(b));
			// System.err.println("my = " + Arrays.toString(my));
			// System.err.println("corr = " + Arrays.toString(corr));
			// throw new AssertionError();
			// }
			// }
		}
	}

	public void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		int[] h = new int[n];
		for (int i = 0; i < n; i++) {
			h[i] = in.nextInt();
		}
		int[] a = new int[m];
		int[] b = new int[m];
		for (int i = 0; i < m; i++) {
			a[i] = in.nextInt() - 1;
			b[i] = in.nextInt();
		}
		int[] res = solve(h, a, b);
		for (int i : res) {
			out.println(i);
		}
	}

	public void run() {
		in = new FastScanner();
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	FastScanner in;
	PrintWriter out;

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(String fileName) {
			try {
				br = new BufferedReader(new FileReader(fileName));
			} catch (FileNotFoundException e) {
			}
		}

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String nextToken() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(nextToken());
		}

		long nextLong() {
			return Long.parseLong(nextToken());
		}

		double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}

	public static void main(String[] args) {
		new D().run();
	}
}