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 CF650D1 {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void solve() throws IOException {
        int t = 1;
        while (t-- > 0) {
            solveTest();
        }
    }

    class Query {
        int index;
        int value;
        int i;

        public Query(int index, int value, int i) {
            this.index = index;
            this.value = value;
            this.i = i;
        }

        public int getIndex() {
            return index;
        }
    }

    class Treap {
        Random rg = new Random();

        Node root;

        class Node {
            Node left, right;
            int key;
            int value;
            int maxValue;
            long prior;

            Node(int key, int value) {
                this.key = key;
                this.value = value;
                this.maxValue = value;
                this.prior = rg.nextLong();
            }
        }

        int getMaxValue(Node node) {
            return node == null ? 0 : node.maxValue;
        }

        void update(Node node) {
            if (node != null) {
                node.maxValue = node.value;
                int left = getMaxValue(node.left);
                if (node.maxValue < left) {
                    node.maxValue = left;
                }
                int right = getMaxValue(node.right);
                if (node.maxValue < right) {
                    node.maxValue = right;
                }
            }
        }

        Node merge(Node left, Node right) {
            if (left == null) return right;
            if (right == null) return left;
            Node res;
            if (left.prior > right.prior) {
                res = merge(left.right, right);
                left.right = res;
                res = left;
            } else {
                res = merge(left, right.left);
                right.left = res;
                res = right;
            }
            update(res);
            return res;
        }

        Node[] split(Node node, int key) {
            if (node == null) return new Node[2];
            Node[] res;
            if (key <= node.key) {
                res = split(node.left, key);
                node.left = res[1];
                res[1] = node;
            } else {
                res = split(node.right, key);
                node.right = res[0];
                res[0] = node;
            }
            update(res[0]);
            update(res[1]);
            return res;
        }

        void add(int key, int value) {
            Node tmp = new Node(key, value);
            Node[] parts = split(root, key);
            root = merge(parts[0], merge(tmp, parts[1]));
        }

        int findMax(int key) {
            Node[] parts = split(root, key);
            int res = getMaxValue(parts[0]);
            root = merge(parts[0], parts[1]);
            return res;
        }

        int findMaxRev(int key) {
            Node[] parts = split(root, key + 1);
            int res = getMaxValue(parts[1]);
            root = merge(parts[0], parts[1]);
            return res;
        }
    }

    class SegmentTree {
        int[] t;
        int n;

        SegmentTree(int n) {
            this.n = n;
            t = new int[4*n];
        }

        int getMax(int left, int right) {
            return getMax(0, left, right, 0, n-1);
        }


        int getMax(int v, int al, int ar, int tl, int tr) {
            if(al > ar) {
                return 0;
            }
            if(al == tl && ar == tr) {
                return t[v];
            }
            int tm = (tl+tr) >> 1;
            int left = getMax((v << 1) + 1, al, Math.min(tm, ar), tl, tm);
            int right = getMax((v << 1) + 2, Math.max(tm+1, al), ar, tm+1, tr);
            return left < right ? right : left;
        }

        void update(int index, int value) {
            int v = 0;
            int tl = 0;
            int tr = n-1;
            do {
                if(value > t[v]) {
                    t[v] = value;
                }
                if(tl == tr) break;
                int tm = (tl + tr) >> 1;
                v = (v << 1) + 1;
                if(index <= tm) {
                    tr = tm;
                } else {
                    tl = tm+1;
                    v++;
                }
            } while (true);
        }
    }

    private void solveTest() throws IOException {
        int n = readInt();
        int m = readInt();
        int[] h = readArr(n);

        int[] hs = new int[n];
        for(int i = 0; i < n; i++) {
            hs[i] = h[i];
        }
        Arrays.sort(hs);

        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(0, 0);
        int x = 1;
        map.put(hs[0], x++);
        for(int i = 1; i < n; i++) {
            if(hs[i] != hs[i-1]) {
                map.put(hs[i], x++);
            }
        }
        map.put(1000 * 1000 * 1000 + 8, x++);

        for(int i = 0; i < n; i++) {
            h[i] = map.get(h[i]);
        }
        Query[] queries = new Query[m];
        for (int i = 0; i < m; i++) {
            queries[i] = new Query(readInt() - 1, readInt(), i);
        }
        Arrays.sort(queries, Comparator.comparingLong(Query::getIndex));


        int[] left = new int[n];
        int[] qLeft = new int[m];
        int[] right = new int[n];
        int[] qRight = new int[m];
        int[] positionsCount = new int[n + 1];
        SegmentTree leftST = new SegmentTree(x);
        int pointer = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            while (pointer < m) {
                if (queries[pointer].index > i) {
                    break;
                }
                int lefted = map.lowerEntry(queries[pointer].value).getValue();
                qLeft[queries[pointer].i] = leftST.getMax(0, lefted) + 1;
                pointer++;
            }
            left[i] = leftST.getMax(0, h[i] - 1) + 1;
            leftST.update(h[i], left[i]);
            if (max < left[i]) {
                max = left[i];
            }
        }
        pointer = m - 1;
        SegmentTree rightST = new SegmentTree(x);
        for (int i = n - 1; i >= 0; i--) {
            while (pointer >= 0) {
                if (queries[pointer].index < i) break;
                int righted = map.higherEntry(queries[pointer].value).getValue();
                qRight[queries[pointer].i] = rightST.getMax(righted, x-1) + 1;
                pointer--;
            }
            right[i] = rightST.getMax(h[i] + 1, x-1) + 1;
            rightST.update(h[i], right[i]);
        }
        for (int i = 0; i < n; i++) {
            if (left[i] + right[i] - 1 == max) {
                positionsCount[left[i]]++;
            }
        }

        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            Query q = queries[i];

            int index = q.index;
            int oldRes = left[index] + right[index] - 1;

            int res = qLeft[q.i] + qRight[q.i] - 1;
            if (res < max) {
                if(oldRes != max) {
                    ans[q.i] = max;
                } else {
                    int l = left[index];
                    if (positionsCount[l] == 1) {
                        ans[q.i] = max - 1;
                    } else {
                        ans[q.i] = max;
                    }
                }
            } else {
                ans[q.i] = res;
            }

        }

        for (int i = 0; i < m; i++) {
            out.println(ans[i]);
        }
    }

    int get(Map<Long, Integer> map, long key) {
        if (!map.containsKey(key)) {
            return 0;
        }
        return map.get(key);
    }

    void add(Map<Long, Integer> map, long key) {
        if (!map.containsKey(key)) {
            map.put(key, 0);
        }
        map.put(key, map.get(key) + 1);
    }

    void remove(Map<Long, Integer> map, long key) {
        Integer count = map.get(key);
        if (count.equals(0)) {
            map.remove(key);
        } else {
            map.put(key, count - 1);
        }
    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " .");
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    int[] readArr(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long[] readArrL(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = readLong();
        }
        return res;
    }

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

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }
}