Alyona has built n towers by putting small cubes some on the top of others. Each cube has size 1 × 1 × 1. A tower is a non-zero amount of cubes standing on the top of each other. The towers are next to each other, forming a row.

Sometimes Alyona chooses some segment towers, and put on the top of each tower several cubes. Formally, Alyouna chooses some segment of towers from li to ri and adds di cubes on the top of them.

Let the sequence a1, a2, ..., an be the heights of the towers from left to right. Let's call as a segment of towers al, al + 1, ..., ar a hill if the following condition holds: there is integer k (l ≤ k ≤ r) such that al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar.

After each addition of di cubes on the top of the towers from li to ri, Alyona wants to know the maximum width among all hills. The width of a hill is the number of towers in it.

Input

The first line contain single integer n (1 ≤ n ≤ 3·105) — the number of towers.

The second line contain n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the number of cubes in each tower. 

The third line contain single integer m (1 ≤ m ≤ 3·105) — the number of additions.

The next m lines contain 3 integers each. The i-th of these lines contains integers li, ri and di (1 ≤ l ≤ r ≤ n, 1 ≤ di ≤ 109), that mean that Alyona puts di cubes on the tio of each of the towers from li to ri.

Output

Print m lines. In i-th line print the maximum width of the hills after the i-th addition.

Example

Input

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


Output

2
4
5

Note

The first sample is as follows:

After addition of 2 cubes on the top of each towers from the first to the third, the number of cubes in the towers become equal to [7, 7, 7, 5, 5]. The hill with maximum width is [7, 5], thus the maximum width is 2.

After addition of 1 cube on the second tower, the number of cubes in the towers become equal to [7, 8, 7, 5, 5]. The hill with maximum width is now [7, 8, 7, 5], thus the maximum width is 4.

After addition of 1 cube on the fourth tower, the number of cubes in the towers become equal to [7, 8, 7, 6, 5]. The hill with maximum width is now [7, 8, 7, 6, 5], thus the maximum width is 5.
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.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);
            CAlyonaAndTowers solver = new CAlyonaAndTowers();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CAlyonaAndTowers {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int[] a = new int[n];
            in.populate(a);
            int m = in.readInt();
            Segment seg = new Segment(1, n, i -> a[i - 1]);
            for (int i = 0; i < m; i++) {
                int l = in.readInt();
                int r = in.readInt();
                int d = in.readInt();

                seg.update(l, r, 1, n, d);

                //seg.toString();
                int ans = seg.state.hill;
                out.println(ans);
            }
        }

    }

    static interface IntToIntegerFunction {
        int apply(int x);

    }

    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 State implements Cloneable {
        long h;
        long t;
        int hill;
        int size;
        int[] head = new int[3];
        int[] tail = new int[3];

        public void modify(long x) {
            h += x;
            t += x;
        }

        public void init(long x) {
            h = t = x;
            hill = 1;
            size = 1;
            Arrays.fill(head, 1);
            Arrays.fill(tail, 1);
        }

        public static void mergeInto(State a, State b, State ans) {
            ans.h = a.h;
            ans.t = b.t;
            ans.size = a.size + b.size;
            ans.hill = Math.max(a.hill, b.hill);
            if (a.t < b.h) {
                ans.hill = Math.max(ans.hill, a.tail[0] + b.head[2]);
            } else if (a.t > b.h) {
                ans.hill = Math.max(ans.hill, a.tail[2] + b.head[1]);
            }

            for (int i = 0; i < 3; i++) {
                ans.head[i] = a.head[i];
                ans.tail[i] = b.tail[i];
            }

            //concate
            if (a.t < b.h) {
                if (a.head[0] == a.size) {
                    ans.head[0] = Math.max(ans.head[0], a.head[0] + b.head[0]);
                    ans.head[2] = Math.max(ans.head[2], a.head[0] + b.head[2]);
                }
                if (b.tail[0] == b.size) {
                    ans.tail[0] = Math.max(ans.tail[0], a.tail[0] + b.tail[0]);
                }
                if (b.tail[2] == b.size) {
                    ans.tail[2] = Math.max(ans.tail[2], a.tail[0] + b.tail[2]);
                }
            } else if (a.t > b.h) {
                if (a.head[1] == a.size) {
                    ans.head[1] = Math.max(ans.head[1], a.head[1] + b.head[1]);
                }
                if (a.head[2] == a.size) {
                    ans.head[2] = Math.max(ans.head[2], a.head[2] + b.head[1]);
                }
                if (b.tail[1] == b.size) {
                    ans.tail[1] = Math.max(ans.tail[1], a.tail[1] + b.tail[1]);
                    ans.tail[2] = Math.max(ans.tail[2], a.tail[2] + b.tail[1]);
                }
            }

            for (int i = 0; i < 2; i++) {
                ans.tail[2] = Math.max(ans.tail[2], ans.tail[i]);
                ans.head[2] = Math.max(ans.head[2], ans.head[i]);
            }
        }

        public String toString() {
            return "" + h;
        }

        public State clone() {
            State state = new State();
            state.h = h;
            state.t = t;
            state.size = size;
            state.head = head.clone();
            state.tail = tail.clone();
            return state;
        }

    }

    static class Segment implements Cloneable {
        private Segment left;
        private Segment right;
        State state = new State();
        long plus;

        private void modify(long x) {
            plus += x;
            state.modify(x);
        }

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

        public void pushDown() {
            if (plus != 0) {
                left.modify(plus);
                right.modify(plus);
                plus = 0;
            }
        }

        public Segment(int l, int r, IntToIntegerFunction func) {
            if (l < r) {
                int m = DigitUtils.floorAverage(l, r);
                left = new Segment(l, m, func);
                right = new Segment(m + 1, r, func);
                pushUp();
            } else {
                state.init(func.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 update(int ll, int rr, int l, int r, long 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 {
                Segment ans = (Segment) super.clone();
                ans.state = state.clone();
                return ans;
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        private void toString(StringBuilder builder) {
            if (left == null && right == null) {
                builder.append(state.h).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 DigitUtils {
        private DigitUtils() {
        }

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

    }

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

    }
}

