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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DZipLine solver = new DZipLine();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DZipLine {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();
            int[] h = new int[n];
            in.populate(h);
            Query[] qs = new Query[m];
            MultiWayStack<Query> stack = new MultiWayStack<>(n, m);
            for (int i = 0; i < m; i++) {
                int a = in.readInt() - 1;
                qs[i] = new Query();
                qs[i].x = in.readInt();
                stack.addLast(a, qs[i]);
            }

            //backward
            int inf = (int) 2e9;
            int[] lis = new int[n];

            int[] dp = new int[n];
            Arrays.fill(dp, inf);
            for (int i = 0; i < n; i++) {
                int wpos = SequenceUtils.upperBound(dp, h[i], 0, n - 1);
                for (Query q : stack.getStack(i)) {
                    q.left = SequenceUtils.upperBound(dp, q.x, 0, n - 1);
                }
                dp[wpos] = h[i];
                lis[i] = wpos + 1;
            }
            int best = 0;
            while (best + 1 < n && dp[best + 1] < inf) {
                best++;
            }
            best++;

            Arrays.fill(dp, -1);
            for (int i = n - 1; i >= 0; i--) {
                int wpos = SequenceUtils.lowerBound(dp, h[i], 0, n - 1);
                for (Query q : stack.getStack(i)) {
                    q.right = n - 1 - SequenceUtils.lowerBound(dp, q.x, 0, n - 1);
                }
                dp[wpos] = h[i];
            }

            boolean[] added = new boolean[n];
            int[] active = new int[n + 2];
            int[] highest = new int[n + 2];
            for (int i = n - 1; i >= 0; i--) {
                if (lis[i] == best || highest[lis[i] + 1] > h[i]) {
                    active[lis[i]]++;
                    highest[lis[i]] = Math.max(highest[lis[i]], h[i]);
                    added[i] = true;
                }
            }

            for (int i = 0; i < n; i++) {
                boolean necessary = added[i] && active[lis[i]] == 1;
                int cand = necessary ? best - 1 : best;

                for (Query q : stack.getStack(i)) {
                    q.ans = Math.max(cand, q.left + q.right + 1);
                }
            }

            for (Query q : qs) {
                out.println(q.ans);
            }
        }

    }

    static interface RevokeIterator<E> extends Iterator<E> {
    }

    static class Query {
        int x;
        int ans;
        int left;
        int right;

    }

    static class MultiWayStack<T> {
        private Object[] values;
        private int[] next;
        private int[] heads;
        private int alloc;
        private int stackNum;

        public RevokeIterator<T> iterator(final int queue) {
            return new RevokeIterator<T>() {
                int ele = heads[queue];
                int pre = 0;


                public boolean hasNext() {
                    return ele != 0;
                }


                public T next() {
                    T ans = (T) values[ele];
                    pre = ele;
                    ele = next[ele];
                    return ans;
                }


                public void revoke() {
                    ele = pre;
                    pre = 0;
                }
            };
        }

        public SimplifiedStack<T> getStack(int qId) {
            return new SimplifiedStack<T>() {

                public boolean isEmpty() {
                    return MultiWayStack.this.isEmpty(qId);
                }


                public T peekLast() {
                    return MultiWayStack.this.peekLast(qId);
                }


                public void addLast(T x) {
                    MultiWayStack.this.addLast(qId, x);
                }


                public T removeLast() {
                    return MultiWayStack.this.removeLast(qId);
                }


                public Iterator<T> iterator() {
                    return MultiWayStack.this.iterator(qId);
                }
            };
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            values = Arrays.copyOf(values, newSize);
        }

        public void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
        }

        public boolean isEmpty(int qId) {
            return heads[qId] == 0;
        }

        public MultiWayStack(int qNum, int totalCapacity) {
            values = new Object[totalCapacity + 1];
            next = new int[totalCapacity + 1];
            heads = new int[qNum];
            stackNum = qNum;
        }

        public void addLast(int qId, T x) {
            alloc();
            values[alloc] = x;
            next[alloc] = heads[qId];
            heads[qId] = alloc;
        }

        public T peekLast(int qId) {
            return (T) values[heads[qId]];
        }

        public T removeLast(int qId) {
            T ans = (T) values[heads[qId]];
            heads[qId] = next[heads[qId]];
            return ans;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < stackNum; i++) {
                builder.append(i).append(": ");
                for (Iterator iterator = iterator(i); iterator.hasNext(); ) {
                    builder.append(iterator.next()).append(",");
                }
                if (builder.charAt(builder.length() - 1) == ',') {
                    builder.setLength(builder.length() - 1);
                }
                builder.append('\n');
            }
            return builder.toString();
        }

    }

    static interface SimplifiedStack<T> extends Iterable<T> {
    }

    static class SequenceUtils {
        public static int upperBound(int[] data, int x, int l, int r) {
            int excess = r + 1;
            while (l < r) {
                int m = (l + r) >>> 1;
                if (data[m] < x) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            return data[l] >= x ? l : excess;
        }

        public static int lowerBound(int[] data, int x, int l, int r) {
            int excess = l - 1;
            while (l < r) {
                int m = (l + r + 1) >>> 1;
                if (data[m] <= x) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
            return data[l] <= x ? l : excess;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}

