Problem: On the 228-th international Uzhlyandian Wars strategic game tournament teams from each country are called. The teams should consist of 5 participants.

The team of Uzhlyandia will consist of soldiers, because there are no gamers.

Masha is a new minister of defense and gaming. The prime duty of the minister is to calculate the efficiency of the Uzhlandian army. The army consists of n soldiers standing in a row, enumerated from 1 to n. For each soldier we know his skill in Uzhlyandian Wars: the i-th soldier's skill is ai.

It was decided that the team will consist of three players and two assistants. The skills of players should be same, and the assistants' skills should not be greater than the players' skill. Moreover, it is important for Masha that one of the assistants should stand in the row to the left of the players, and the other one should stand in the row to the right of the players. Formally, a team is five soldiers with indexes i, j, k, l, p, such that 1 ≤ i < j < k < l < p ≤ n and ai ≤ aj = ak = al ≥ ap. 

The efficiency of the army is the number of different teams Masha can choose. Two teams are considered different if there is such i such that the i-th soldier is a member of one team, but not a member of the other team.

Initially, all players are able to be players. For some reasons, sometimes some soldiers become unable to be players. Sometimes some soldiers, that were unable to be players, become able to be players. At any time any soldier is able to be an assistant. Masha wants to control the efficiency of the army, so she asked you to tell her the number of different possible teams modulo 1000000007 (109 + 7) after each change. 

Input

The first line contains single integer n (1 ≤ n ≤ 105) — the number of soldiers in Uzhlyandia.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the soldiers' skills.

The third line contains single integer m (1 ≤ m ≤ 105) — the number of changes.

The next m lines contain the changes, each change is described with two integers t and x (1 ≤ t ≤ 2, 1 ≤ x ≤ n) on a separate line. If t = 1, then the x-th soldier is unable to be a player after this change. If t = 2, then the x-th soldier is able to be a player after this change. 

It is guaranteed that before each query of the first type the soldier is able to be a player, and before each query of the second type the soldier is unable to be a player.

Output

Print m integers — the number of distinct teams after each change.

Print the answers modulo 1000000007 (109 + 7). 

Examples

Input

6
1 1 1 1 1 1
2
1 3
2 3


Output

1
6


Input

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


Output

1
6
2

Note

In the first example, after the first change the only team consists of soldiers [1, 2, 4, 5, 6]. After the second change any five soldiers can form a team.

In the first example after the first change the only team is soldiers [1, 2, 3, 7, 8]. After the second change the possible teams are: [1, 2, 3, 5, 7], [1, 2, 3, 5, 8], [1, 2, 3, 7, 8], [1, 2, 5, 7, 8], [1, 3, 5, 7, 8], [2, 3, 5, 7, 8]. After the third change the possible teams are: [1, 3, 5, 7, 8], [2, 3, 5, 7, 8].

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.util.Random;
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);
            ENewTask solver = new ENewTask();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class ENewTask {
        Modular mod = new Modular(1000000007);
        Debug debug = new Debug(false);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            debug.elapse("init");
            int n = in.readInt();
            int[] a = new int[n];
            in.populate(a);
            IntegerDiscreteMap idm = new IntegerDiscreteMap(a.clone(), 0, a.length);
            for (int i = 0; i < n; i++) {
                a[i] = idm.rankOf(a[i]);
            }
            IntegerMultiWayStack valueStack = new IntegerMultiWayStack(idm.maxRank() + 1, n);
            for (int i = 0; i < n; i++) {
                valueStack.addLast(a[i], i);
            }
            int m = in.readInt();
            int[] tags = new int[m];
            int[][] events = new int[m][2];
            for (int i = 0; i < m; i++) {
                events[i][0] = in.readInt();
                events[i][1] = in.readInt() - 1;
            }
            IntegerMultiWayDeque eventStack = new IntegerMultiWayDeque(idm.maxRank() + 1, m);
            for (int i = 0; i < m; i++) {
                eventStack.addLast(a[events[i][1]], i);
            }
            debug.elapse("read data");

            Segment seg = new Segment(0, n);

            for (int i = 0; i <= idm.maxRank(); i++) {
                for (IntegerIterator iterator = valueStack.iterator(i); iterator.hasNext(); ) {
                    int next = iterator.next();
                    seg.update(next, next, 0, n, 1);
                }
                debug.elapse("add 1");
                int cur = seg.state.cnt[State.ai.indexOf(0, 4)];
                //debug.debug("seg.state.cnt", seg.state.cnt, State.ai);
                tags[0] = mod.plus(tags[0], cur);

                for (IntegerIterator iterator = eventStack.iterator(i); iterator.hasNext(); ) {
                    int index = iterator.next();
                    int how = events[index][0];
                    int which = events[index][1];
                    if (how == 1) {
                        //can't be used again
                        seg.update(which, which, 0, n, 0);
                    } else {
                        seg.update(which, which, 0, n, 1);
                    }

                    int now = seg.state.cnt[State.ai.indexOf(0, 4)];
                    int delta = now - cur;
                    tags[index] = mod.plus(tags[index], delta);
                    cur = now;
                }
                debug.elapse("handle event");

                for (IntegerIterator iterator = valueStack.iterator(i); iterator.hasNext(); ) {
                    int next = iterator.next();
                    seg.update(next, next, 0, n, 0);
                }
                debug.elapse("add 0");
            }

            for (int i = 1; i < m; i++) {
                tags[i] = mod.plus(tags[i - 1], tags[i]);
            }

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

            debug.elapse("output");
        }

    }

    static class State {
        static long mod = 1000000007;
        static ArrayIndex ai = new ArrayIndex(5, 5);
        int[] cnt = new int[ai.totalSize()];

        public void init(int x) {
            if (x == 0) {
                for (int i = 0; i < 5; i++) {
                    cnt[ai.indexOf(i, i)] = 0;
                }
                cnt[ai.indexOf(0, 0)] = cnt[ai.indexOf(4, 4)] = 1;
            } else if (x == 1) {
                for (int i = 0; i < 5; i++) {
                    cnt[ai.indexOf(i, i)] = 1;
                }
            }
        }

        public void mergeInto(State a, State b) {
            for (int i = 0; i < 5; i++) {
                for (int j = i; j < 5; j++) {
                    long ans = a.cnt[ai.indexOf(i, j)] + b.cnt[ai.indexOf(i, j)];
                    for (int k = i; k < j; k++) {
                        ans += (long) a.cnt[ai.indexOf(i, k)] * b.cnt[ai.indexOf(k + 1, j)] % mod;
                    }
                    cnt[ai.indexOf(i, j)] = (int) (ans % mod);
                }
            }
        }

        public String toString() {
            return Arrays.toString(cnt);
        }

    }

    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 StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        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;
        }

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

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

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

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

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

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

        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();
        }

    }

    static class RandomWrapper {
        private Random random;
        public static RandomWrapper INSTANCE = new RandomWrapper(new Random());

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        private long time = System.currentTimeMillis();

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug elapse(String name) {
            if (offline) {
                debug(name, System.currentTimeMillis() - time);
                time = System.currentTimeMillis();
            }
            return this;
        }

        public Debug debug(String name, long x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

    }

    static class ArrayIndex {
        int[] dimensions;

        public ArrayIndex(int... dimensions) {
            this.dimensions = dimensions;
        }

        public int totalSize() {
            int ans = 1;
            for (int x : dimensions) {
                ans *= x;
            }
            return ans;
        }

        public int indexOf(int a, int b) {
            return a * dimensions[1] + b;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static class IntegerMultiWayDeque {
        private int[] values;
        private int[] next;
        private int[] prev;
        private int[] heads;
        private int[] tails;
        private int alloc;
        private int queueNum;

        public IntegerIterator iterator(final int queue) {
            return new IntegerIterator() {
                int ele = heads[queue];


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


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

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            prev = Arrays.copyOf(prev, 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 IntegerMultiWayDeque(int qNum, int totalCapacity) {
            values = new int[totalCapacity + 1];
            next = new int[totalCapacity + 1];
            prev = new int[totalCapacity + 1];
            heads = new int[qNum];
            tails = new int[qNum];
            queueNum = qNum;
        }

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

            if (heads[qId] == 0) {
                heads[qId] = tails[qId] = alloc;
                return;
            }
            next[tails[qId]] = alloc;
            prev[alloc] = tails[qId];
            tails[qId] = alloc;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < queueNum; i++) {
                if (isEmpty(i)) {
                    continue;
                }
                builder.append(i).append(": ");
                for (IntegerIterator 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 class Segment implements Cloneable {
        private Segment left;
        private Segment right;
        State state = new State();

        private void modify(int x) {
            state.init(x);
        }

        public void pushUp() {
            state.mergeInto(left.state, right.state);
        }

        public void pushDown() {
        }

        public Segment(int l, int r) {
            if (l < r) {
                int m = DigitUtils.floorAverage(l, r);
                left = new Segment(l, m);
                right = new Segment(m + 1, r);
                pushUp();
            } else {
                modify(2);
            }
        }

        private boolean covered(int ll, int rr, int l, int r) {
            return ll <= l && rr >= r;
        }

        private boolean noIntersection(int ll, int rr, int l, int r) {
            return ll > r || rr < l;
        }

        public void update(int ll, int rr, int l, int r, int x) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                modify(x);
                return;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            left.update(ll, rr, l, m, x);
            right.update(ll, rr, m + 1, r, x);
            pushUp();
        }

        private Segment deepClone() {
            Segment seg = clone();
            if (seg.left != null) {
                seg.left = seg.left.deepClone();
            }
            if (seg.right != null) {
                seg.right = seg.right.deepClone();
            }
            return seg;
        }

        protected Segment clone() {
            try {
                return (Segment) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        private void toString(StringBuilder builder) {
            if (left == null && right == null) {
                builder.append("val").append(",");
                return;
            }
            pushDown();
            left.toString(builder);
            right.toString(builder);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            deepClone().toString(builder);
            if (builder.length() > 0) {
                builder.setLength(builder.length() - 1);
            }
            return builder.toString();
        }

    }

    static class IntegerMultiWayStack {
        private int[] values;
        private int[] next;
        private int[] heads;
        private int alloc;
        private int stackNum;

        public IntegerIterator iterator(final int queue) {
            return new IntegerIterator() {
                int ele = heads[queue];


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


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

        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 IntegerMultiWayStack(int qNum, int totalCapacity) {
            values = new int[totalCapacity + 1];
            next = new int[totalCapacity + 1];
            heads = new int[qNum];
            stackNum = qNum;
        }

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

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < stackNum; i++) {
                if (isEmpty(i)) {
                    continue;
                }
                builder.append(i).append(": ");
                for (IntegerIterator 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 class Randomized {
        public static void shuffle(int[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                int tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static int nextInt(int l, int r) {
            return RandomWrapper.INSTANCE.nextInt(l, r);
        }

    }

    static class Modular {
        int m;

        public Modular(int m) {
            this.m = m;
        }

        public Modular(long m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public Modular(double m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public int valueOf(int x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return x;
        }

        public int plus(int x, int y) {
            return valueOf(x + y);
        }

        public String toString() {
            return "mod " + m;
        }

    }

    static class IntegerDiscreteMap {
        int[] val;
        int f;
        int t;

        public IntegerDiscreteMap(int[] val, int f, int t) {
            Randomized.shuffle(val, f, t);
            Arrays.sort(val, f, t);
            int wpos = f + 1;
            for (int i = f + 1; i < t; i++) {
                if (val[i] == val[i - 1]) {
                    continue;
                }
                val[wpos++] = val[i];
            }
            this.val = val;
            this.f = f;
            this.t = wpos;
        }

        public int rankOf(int x) {
            return Arrays.binarySearch(val, f, t, x) - f;
        }

        public int maxRank() {
            return t - f - 1;
        }

        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(val, f, t));
        }

    }
}