Problem: There are n officers in the Army of Byteland. Each officer has some power associated with him. The power of the i-th officer is denoted by p_{i}. As the war is fast approaching, the General would like to know the strength of the army.

The strength of an army is calculated in a strange way in Byteland. The General selects a random subset of officers from these n officers and calls this subset a battalion.(All 2^n subsets of the n officers can be chosen equally likely, including empty subset and the subset of all officers).

The strength of a battalion is calculated in the following way:

Let the powers of the chosen officers be a_{1},a_{2},…,a_{k}, where a_1 ≤ a_2 ≤ ... ≤ a_k. The strength of this battalion is equal to a_1a_2 + a_2a_3 + ... + a_{k-1}a_k. (If the size of Battalion is ≤ 1, then the strength of this battalion is 0).

The strength of the army is equal to the expected value of the strength of the battalion.

As the war is really long, the powers of officers may change. Precisely, there will be q changes. Each one of the form i x indicating that p_{i} is changed to x.

You need to find the strength of the army initially and after each of these q updates.

Note that the changes are permanent.

The strength should be found by modulo 10^{9}+7. Formally, let M=10^{9}+7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and qnot≡ 0 mod M). Output the integer equal to p⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p mod M).

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 3⋅10^{5}) — the number of officers in Byteland's Army.

The second line contains n integers p_{1},p_{2},…,p_{n} (1 ≤ p_{i} ≤ 10^{9}).

The third line contains a single integer q (1 ≤ q ≤ 3⋅10^{5}) — the number of updates.

Each of the next q lines contains two integers i and x (1 ≤ i ≤ n,  1 ≤ x ≤ 10^{9}), indicating that p_{i} is updated to x .

Output

In the first line output the initial strength of the army.

In i-th of the next q lines, output the strength of the army after i-th update.

Examples

Input


2
1 2
2
1 2
2 1


Output


500000004
1
500000004


Input


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


Output


625000011
13
62500020
375000027
62500027

Note

In first testcase, initially, there are four possible battalions 

  * {} Strength = 0 
  * {1} Strength = 0 
  * {2} Strength = 0 
  * {1,2} Strength = 2 

So strength of army is (0+0+0+2)/(4) = 1/2

After changing p_{1} to 2, strength of battallion {1,2} changes to 4, so strength of army becomes 1.

After changing p_{2} to 1, strength of battalion {1,2} again becomes 2, so strength of army becomes 1/2.

Solution (in JAVA):

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

    static class FBattalionStrength {
        Modular mod = new Modular(1e9 + 7);
        Power power = new Power(mod);

        public void solve(int testNumber, FastInput in, FastOutput out) {

            int inv2 = power.inverseByFermat(2);

            int n = in.readInt();
            int[] val = new int[n + 1];

            for (int i = 1; i <= n; i++) {
                int x = in.readInt();
                val[i] = x;
                //root = add(root, create(x));
            }

            int q = in.readInt();
            int[][] qs = new int[q][2];
            for (int i = 0; i < q; i++) {
                for (int j = 0; j < 2; j++) {
                    qs[i][j] = in.readInt();
                }
            }

            IntegerList list = new IntegerList(n + q);
            for (int i = 1; i <= n; i++) {
                list.add(val[i]);
            }
            for (int i = 0; i < q; i++) {
                list.add(qs[i][1]);
            }
            IntegerDiscreteMap dm = new IntegerDiscreteMap(list.getData(), 0, list.size());
            Segment seg = new Segment(dm.minRank(), dm.maxRank(), i -> dm.iThElement(i));
            //debug.debug("1/2(1/4+13)", mod.mul(inv2, mod.plus(power.inverseByFermat(4), 13)));
            //debug.debug("11/2", mod.mul(inv2, 11));
            for (int i = 1; i <= n; i++) {
                val[i] = dm.rankOf(val[i]);
            }
            for (int i = 0; i < q; i++) {
                qs[i][1] = dm.rankOf(qs[i][1]);
            }

            for (int i = 1; i <= n; i++) {
                seg.add(val[i], val[i], dm.minRank(), dm.maxRank());
            }

            out.println(mod.mul(inv2, seg.exp));
            for (int i = 0; i < q; i++) {
                // debug.debug("i", i);
                int index = qs[i][0];
                int x = qs[i][1];
                seg.remove(val[index], val[index], dm.minRank(), dm.maxRank());
                val[index] = x;
                seg.add(val[index], val[index], dm.minRank(), dm.maxRank());
                out.println(mod.mul(inv2, seg.exp));
            }
        }

    }

    static class SequenceUtils {
        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static class Power {
        final Modular modular;

        public Power(Modular modular) {
            this.modular = modular;
        }

        public int pow(int x, int n) {
            if (n == 0) {
                return modular.valueOf(1);
            }
            long r = pow(x, n >> 1);
            r = modular.valueOf(r * r);
            if ((n & 1) == 1) {
                r = modular.valueOf(r * x);
            }
            return (int) r;
        }

        public int inverseByFermat(int x) {
            return pow(x, modular.m - 2);
        }

    }

    static class Randomized {
        private static Random random = new Random(0);

        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 random.nextInt(r - l + 1) + l;
        }

    }

    static class IntegerList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public int[] getData() {
            return data;
        }

        public IntegerList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerList(IntegerList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerList list) {
            addAll(list.data, 0, list.size);
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

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

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerList)) {
                return false;
            }
            IntegerList other = (IntegerList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerList clone() {
            IntegerList ans = new IntegerList();
            ans.addAll(this);
            return ans;
        }

    }

    static class Segment implements Cloneable {
        private Segment left;
        private Segment right;
        private int size;
        private int sumX;
        private int sumY;
        public int exp;
        private int x;
        static Modular mod = new Modular(1e9 + 7);
        static CachedPow pow = new CachedPow(2, mod);

        public void pushUp() {
            size = left.size + right.size;
            int pos = mod.mul(right.sumX, pow.pow(left.size));
            int neg = mod.mul(right.sumY, pow.inverse(left.size));
            sumX = mod.plus(left.sumX, pos);
            sumY = mod.plus(left.sumY, neg);

            exp = mod.plus(left.exp, right.exp);
            exp = mod.plus(exp, mod.mul(left.sumX, neg));
        }

        public void pushDown() {
        }

        public void remove() {
            size--;
            int pos = mod.mul(x, pow.pow(size));
            int inv = mod.mul(x, pow.inverse(size));
            sumX = mod.subtract(sumX, pos);
            sumY = mod.subtract(sumY, inv);
            exp = mod.subtract(exp, mod.mul(sumX, inv));
        }

        public void add() {
            int pos = mod.mul(x, pow.pow(size));
            int inv = mod.mul(x, pow.inverse(size));
            exp = mod.plus(exp, mod.mul(sumX, inv));
            sumX = mod.plus(sumX, pos);
            sumY = mod.plus(sumY, inv);
            size++;
        }

        public Segment(int l, int r, IntToIntFunction function) {
            if (l < r) {
                int m = (l + r) >> 1;
                left = new Segment(l, m, function);
                right = new Segment(m + 1, r, function);
                pushUp();
            } else {
                x = function.apply(l);
            }
        }

        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 add(int ll, int rr, int l, int r) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                add();
                return;
            }
            pushDown();
            int m = (l + r) >> 1;
            left.add(ll, rr, l, m);
            right.add(ll, rr, m + 1, r);
            pushUp();
        }

        public void remove(int ll, int rr, int l, int r) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                remove();
                return;
            }
            pushDown();
            int m = (l + r) >> 1;
            left.remove(ll, rr, l, m);
            right.remove(ll, rr, m + 1, r);
            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 interface IntToIntFunction {
        int apply(int x);

    }

    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 iThElement(int i) {
            return val[f + i];
        }

        public int minRank() {
            return 0;
        }

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

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

    }

    static class CachedPow {
        private int[] first;
        private int[] second;
        private Modular mod;
        private Modular powMod;
        private static int step = 16;
        private static int limit = 1 << step;
        private static int mask = limit - 1;

        public CachedPow(int x, Modular mod) {
            this(x, mod.getMod(), mod);
        }

        public CachedPow(int x, int maxExp, Modular mod) {
            this.mod = mod;
            this.powMod = mod.getModularForPowerComputation();
            first = new int[limit];
            second = new int[maxExp / limit + 1];
            first[0] = 1;
            for (int i = 1; i < first.length; i++) {
                first[i] = mod.mul(x, first[i - 1]);
            }
            second[0] = 1;
            int step = mod.mul(x, first[first.length - 1]);
            for (int i = 1; i < second.length; i++) {
                second[i] = mod.mul(second[i - 1], step);
            }
        }

        public int pow(int exp) {
            return mod.mul(first[exp & mask], second[exp >> step]);
        }

        public int inverse(int exp) {
            return pow(powMod.valueOf(-exp));
        }

    }

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

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

        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 Modular {
        int m;

        public int getMod() {
            return 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 valueOf(long x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return (int) x;
        }

        public int mul(int x, int y) {
            return valueOf((long) x * y);
        }

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

        public int subtract(int x, int y) {
            return valueOf(x - y);
        }

        public Modular getModularForPowerComputation() {
            return new Modular(m - 1);
        }

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

    }

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

    }
}