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.*;
import java.math.*;
import java.util.*;

public class Main {

	InputReader in;
	PrintWriter out;

	Main() throws IOException {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		// in = new InputReader(new FileInputStream("input_.txt"));
		// out = new PrintWriter(new File("output_.txt"));
		solve();
		out.close();
	}

	public static void main(String args[]) {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// --------------------My Code Starts Here----------------------
	long mod = (long) 1e9 + 7;
	double eps = 1e-5;

	public void solve() throws IOException {
		int n = in.nextInt();
		long a[] = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextLong();
		}
		SegmentTree seg = new SegmentTree(a);
		int q = in.nextInt();
		while (q-- > 0) {
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			int d = in.nextInt();
			// for (int i = l; i <= r; i++)
			// seg.update(1, 0, n - 1, i, d);
			seg.update(1, 0, n - 1, l, r, d);
			out.println(seg.mountain[1]);
		}
	}

	// 0 0 0 0
	// 0 -2 0 0
	// ---------------------My Code Ends Here----------------------
	class SegmentTree {
		long[] left;
		long[] right;
		int[] rightUp;
		int[] leftDown;
		int[] mountain;
		int[] leftMountain;
		int[] rightMountain;
		int[] length;
		int n;
		int size;

		long[] delta;
		long[] src;

		SegmentTree(long[] a) {
			n = a.length;
			size = n * 4;
			left = new long[size];
			right = new long[size];
			rightUp = new int[size];
			leftDown = new int[size];
			mountain = new int[size];
			leftMountain = new int[size];
			rightMountain = new int[size];
			length = new int[size];
			delta = new long[size];
			src = a;
			build(1, 0, n - 1);
		}

		void build(int v, int tl, int tr) {
			if (tl == tr) {
				left[v] = right[v] = src[tl];
				rightUp[v] = leftDown[v] = mountain[v] = leftMountain[v] = rightMountain[v] = length[v] = 1;
				return;
			}
			int mid = (tl + tr) >> 1;
			build(v * 2, tl, mid);
			build(v * 2 + 1, mid + 1, tr);
			solve(v, tl, tr);
		}

		void update(int v, int tl, int tr, int l, int r, long d) {
			if (tl >= l && r >= tr) {
				delta[v] += d;
				left[v] += d;
				right[v] += d;
				return;
			}
			if (r < tl || l > tr)
				return;
			pushDown(v);
			int mid = (tl + tr) >> 1;
			update(v * 2, tl, mid, l, r, d);
			update(v * 2 + 1, mid + 1, tr, l, r, d);
			solve(v, tl, tr);
		}

		void pushDown(int root) {
			left[2 * root + 1] += delta[root];
			right[2 * root + 1] += delta[root];
			delta[2 * root + 1] += delta[root];
			left[2 * root] += delta[root];
			right[2 * root] += delta[root];
			delta[2 * root] += delta[root];
			delta[root] = 0;
		}

		// void update(int v, int tl, int tr, int index, long d) {
		// if (tl == tr) {
		// src[tl] += d;
		// left[v] = right[v] = src[tl];
		// rightUp[v] = leftDown[v] = mountain[v] = leftMountain[v] =
		// rightMountain[v] = length[v] = 1;
		// return;
		// }
		// int mid = (tl + tr) >> 1;
		// if (index <= mid) {
		// update(v * 2, tl, mid, index, d);
		// } else {
		// update(v * 2 + 1, mid + 1, tr, index, d);
		// }
		// solve(v, tl, tr);
		// }

		void solve(int v, int tl, int tr) {
			int left_ind = 2 * v;
			int right_ind = left_ind + 1;
			left[v] = left[left_ind];
			right[v] = right[right_ind];
			rightUp[v] = rightUp[right_ind];
			leftDown[v] = leftDown[left_ind];
			mountain[v] = Math.max(mountain[left_ind], mountain[right_ind]);
			leftMountain[v] = leftMountain[left_ind];
			rightMountain[v] = rightMountain[right_ind];
			length[v] = length[left_ind] + length[right_ind];
			if (right[left_ind] < left[right_ind]) {
				if (rightUp[right_ind] == length[right_ind]) {
					rightUp[v] += rightUp[left_ind];
				}
				if (rightMountain[right_ind] == length[right_ind]) {
					rightMountain[v] = length[right_ind] + rightUp[left_ind];
				}
				if (rightUp[left_ind] == length[left_ind]) {
					leftMountain[v] = Math.max(leftMountain[v], length[left_ind] + leftMountain[right_ind]);
				}
				mountain[v] = Math.max(mountain[v], rightUp[left_ind] + leftMountain[right_ind]);
			} else if (right[left_ind] > left[right_ind]) {
				if (leftDown[left_ind] == length[left_ind]) {
					leftDown[v] += leftDown[right_ind];
				}
				if (leftMountain[left_ind] == length[left_ind]) {
					leftMountain[v] = length[left_ind] + leftDown[right_ind];
				}
				if (leftDown[right_ind] == length[right_ind]) {
					rightMountain[v] = Math.max(rightMountain[v], length[right_ind] + rightMountain[left_ind]);
				}
				mountain[v] = Math.max(mountain[v], leftDown[right_ind] + rightMountain[left_ind]);
			}
		}

	}

	static long modulo(long a, long b, long c) {
		long x = 1;
		long y = a;
		while (b > 0) {
			if (b % 2 == 1) {
				x = (x * y) % c;
			}
			y = (y * y) % c; // squaring the base
			b /= 2;
		}
		return x % c;
	}

	static class Node {
		long l;
		double d;

		Node(long ll, double dd) {
			l = ll;
			d = dd;
		}
	}

	static class Pair implements Comparable<Pair> {
		int x;
		int y;

		Pair(int xx, int yy) {
			x = xx;
			y = yy;
		}

		@Override
		public int compareTo(Pair o) {
			if (Long.compare(this.y, o.y) != 0)
				return Long.compare(this.y, o.y);
			else
				return Long.compare(this.x, o.x);
		}
	}

	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public final int nextInt() throws IOException {
			return (int) nextLong();
		}

		public final long nextLong() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
				if (c == -1)
					throw new IOException();
			}
			boolean negative = false;
			if (c == '-') {
				negative = true;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return negative ? (-res) : (res);
		}

		public final int[] readIntBrray(int size) throws IOException {
			int[] arr = new int[size];
			for (int i = 0; i < size; i++)
				arr[i] = nextInt();
			return arr;
		}

		public final String next() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String nextLine() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (c != '\n' && c != -1);
			return res.toString();
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
}