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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class E {
  private static class Task {
    void solve(FastScanner in, PrintWriter out) throws Exception {
      int N = in.nextInt();
      long[] a = in.nextLongArray(N);
      TreeMap<Integer, Integer> left = new TreeMap<>();
      int from = 0;
      for (int i = 0; i < N; i++) {
        if (i == N - 1 || a[i] >= a[i + 1]) {
          left.put(from, i);
          from = i + 1;
        }
      }
      TreeMap<Integer, Integer> right = new TreeMap<>();
      from = N - 1;
      for (int i = N - 2; i >= -1; i--) {
        if (i < 0 || a[i] <= a[i + 1]) {
          right.put(i + 1, from);
          from = i;
        }
      }

      RMQ rmq = new RMQ(N);
      for (Map.Entry<Integer, Integer> entry : left.entrySet()) {
        from = entry.getKey();
        int to = entry.getValue();
        if (!right.containsKey(to)) continue;
        int to2 = right.get(to);
        int width = to2 - from + 1;
        rmq.update(to, width);
      }

      long[] d = new long[N - 1];
      for (int i = 0; i < N - 1; i++) {
        d[i] = a[i + 1] - a[i];
      }
      int M = in.nextInt();
      TreeSet<Integer> tmp = new TreeSet<>();
      for (int i = 0; i < M; i++) {
        int l = in.nextInt() - 1;
        int r = in.nextInt() - 1;
        long v = in.nextInt();
        if (l > 0) {
          long prev = d[l - 1];
          d[l - 1] += v;
          if (prev <= 0 && d[l - 1] > 0) {
            // left merge
            from = left.floorKey(l - 1);
            int to = left.get(l);
            left.remove(l);
            rmq.update(l, 0);
            left.put(from, to);
            tmp.add(from);
          }
          if (prev < 0 && d[l - 1] >= 0) {
            // right cut
            Map.Entry<Integer, Integer> entry = right.floorEntry(l - 1);
            from = entry.getKey();
            int to = entry.getValue();
            right.put(from, l - 1);
            right.put(l, to);
            rmq.update(from, 0);
            tmp.add(left.floorKey(from));
            tmp.add(left.floorKey(l));
          }
        }
        if (r < N - 1) {
          long prev = d[r];
          d[r] -= v;
          if (prev > 0 && d[r] <= 0) {
            // left cut
            Map.Entry<Integer, Integer> entry = left.floorEntry(r);
            from = entry.getKey();
            int to = entry.getValue();
            left.put(from, r);
            left.put(r + 1, to);
            rmq.update(to, 0);
            tmp.add(from);
            tmp.add(r + 1);
          }
          if (prev >= 0 && d[r] < 0) {
            // right merge
            from = right.floorKey(r);
            int to = right.get(r + 1);
            right.remove(r + 1);
            right.put(from, to);
            rmq.update(from, 0);
            tmp.add(left.floorKey(from));
          }
        }

        for (int f : tmp) {
          int k = left.get(f);
          Integer to = right.get(k);
          if (to==null) continue;
          rmq.update(k, to - f + 1);
        }
        tmp.clear();
        out.println(rmq.query(0, N + 1));
      }
    }

    class RMQ {
      private int N;
      private long[] seg;

      RMQ(int M) {
        N = Integer.highestOneBit(M) * 2;
        seg = new long[N * 2];
      }

      public void update(int k, long value) {
        seg[k += N - 1] = value;
        while (k > 0) {
          k = (k - 1) / 2;
          seg[k] = Math.max(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
      }

      //[a, b)
      long query(int a, int b) {
        return query(a, b, 0, 0, N);
      }

      long query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        long x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        long y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return Math.max(x, y);
      }
    }
  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}