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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1

 */
public class c {

	public static void main(String[] args) throws IOException {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = in.nextInt();
		long[] arr = in.nextLongArray(n);
		SegmentTree st = new SegmentTree(n);
		SuperBIT bit = new SuperBIT(n + 2);
		for(int i = 0; i < n - 1; i++) {
			if(arr[i] > arr[i + 1])
				st.update(i + 1, i + 1, 1);
			else if(arr[i] < arr[i + 1])
				st.update(i + 1, i + 1, -1);
		}
		for(int i = 0; i < n; i++) {
			bit.update(i + 1, i + 1, arr[i]);
		}
		int m = in.nextInt();

		//out.println(st.query(1, n));
		for(int qi = 0; qi < m; qi++) {
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			long d = in.nextLong();
			//for(int i = l; i <= r; i++)
			//	arr[i] += d;
			bit.update(l + 1, r + 1, d);
			if(l > 0) {
				long a = bit.query(l, l);
				long b = bit.query(l + 1, l + 1);
				int val = 0;
				if(a > b) val = 1;
				if(a < b) val = -1;
				st.update(l, l, val);
			}
			if(r + 1 < n) {
				long a = bit.query(r + 1, r + 1);
				long b = bit.query(r + 2, r + 2);
				int val = 0;
				if(a > b) val = 1;
				if(a < b) val = -1;
				st.update(r + 1, r + 1, val);
			}
//			for(int i = 0; i < n - 1; i++) {
//				if(arr[i] > arr[i + 1])
//					st.update(i + 1, i + 1, 1);
//				else if(arr[i] < arr[i + 1])
//					st.update(i + 1, i + 1, -1);
//			}
			long ans = st.query(1, n);
			out.println(ans);
			//out.flush();
		}
		
		out.close();
		
	}

	static class SegmentTree {
		int[] val;//, leftNeg, leftPos, rightNeg, rightPos, best;
		int[][] ans;
		int n;
		
		public SegmentTree(int n) {
			this.n = n;
			val = new int[n * 4 + 1];
			//leftNeg = new long[n * 4 + 1];
			//leftPos = new long[n * 4 + 1];
			//rightNeg = new long[n * 4 + 1];
			//rightPos = new long[n * 4 + 1];
			//best = new long[n * 4 + 1];
			ans = new int[n * 4 + 1][5];
			for(int i = 0; i < ans.length; i++)
				ans[i][4] = 1;
		}
		
		void prop(int i) {
		}
		
		void set(int i, int value) {
			val[i] = value;
			ans[i][1] = ans[i][3] = value == 1 ? 1 : 0;
			ans[i][0] = ans[i][2] = value == -1 ? 1 : 0;
		}
		
		void update(int left, int right, int value) {
			update(1, 1, n, left, right, value);
		}
		
		void update(int i, int lr, int rr, int left, int right, int value) {
			//System.out.println(lr + "  " + rr + "  " + left + "  " + right);
			if (lr == left && rr == right)
				set(i, value);
			else {
				prop(i);
				int mid = (lr + rr) / 2;
				if (left <= mid)
					update(i * 2, lr, mid, left, Math.min(mid,  right), value);
				if (mid < right)
					update(i * 2 + 1, mid + 1, rr, Math.max(mid + 1, left), right, value);
				
				int[] ret = ans[i];
				ret[0] = ret[1] = ret[2] = ret[3] = 0;
				ret[4] = 1;
				if(lr <= mid) {
					int[] tmp = ans[i * 2];//ew long[]{leftNeg[i * 2], leftPos[i * 2], rightNeg[i * 2], rightPos[i * 2], best[i * 2]};
					ret[0] = tmp[0];
					ret[1] = tmp[1];
					ret[2] = tmp[2];
					ret[3] = tmp[3];
					ret[4] = tmp[4];
				}
				if (mid < rr) {
					int[] r = ans[i * 2 + 1];//new long[]{leftNeg[i * 2 + 1], leftPos[i * 2 + 1], rightNeg[i * 2 + 1], rightPos[i * 2 + 1], best[i * 2 + 1]};
					int leftLen = (mid - lr + 1);
					int rightLen = (rr - mid);
					
					if(ret[1] == 0)
						ret[4] = Math.max(ret[4], ret[0] + r[2] + r[3] + 1);
					if(r[2] == 0)
						ret[4] = Math.max(ret[4], ret[0] + ret[1] + r[3] + 1);
					ret[4] = Math.max(ret[4], r[4]);
					
					if(r[1] == rightLen) {
						ret[1] = ret[1] + r[1];
						ret[0] = ret[0];
					} else if(r[0] + r[1] == rightLen) {
						int tmp1 = ret[1];
						int tmp0 = ret[0];
						ret[1] = r[1];
						ret[0] = r[0];
						if(tmp1 == 0)
							ret[0] += tmp0;
					} else {
						ret[1] = r[1];
						ret[0] = r[0];
					}
					
					if(leftLen <= 0) {
						ret[2] = r[2];
						ret[3] = r[3];
					} else {
						if(ret[2] == leftLen) {
							ret[2] = ret[2] + r[2];
							ret[3] = r[3];
						} else if(ret[2] + ret[3] == leftLen) {
							if(r[2] == 0)
								ret[3] += r[3];
						} else {
							
						}
					}
					
					ret[4] = Math.max(ret[4], ret[0] + ret[1] + 1);
					ret[4] = Math.max(ret[4], ret[2] + ret[3] + 1);
					
				}
				
				/*
				leftNeg[i] = ret[0];
				leftPos[i] = ret[1];
				rightNeg[i] = ret[2];
				rightPos[i] = ret[3];
				best[i] = ret[4];
				
				//System.out.printf("[%d, %d] = leftNeg: %d, leftPos: %d, rightNeg: %d, rightPos: %d, best: %d\n", lr, rr, leftNeg[i], leftPos[i], rightNeg[i], rightPos[i], best[i]);
				//min[i] = Math.min(min[i * 2], min[i * 2 + 1]);
				//max[i] = Math.max(max[i * 2], max[i * 2 + 1]);
				 */
			}
		}
		
		int query(int left, int right) {
			return query(1, 1, n, left, right)[4];
		}
		
		int[] query(int i, int lr, int rr, int left, int right) {
			if (lr == left && rr == right)
				return ans[i];
			else {
				prop(i);
				int mid = (lr + rr) / 2;
				int[] ret = ans[i];
				ret[0] = ret[1] = ret[2] = ret[3] = 0;
				ret[4] = 1;
				if (left <= mid) {
					int[] tmp = query(i * 2, lr, mid, left, Math.min(mid, right));
					ret[0] = tmp[0];
					ret[1] = tmp[1];
					ret[2] = tmp[2];
					ret[3] = tmp[3];
					ret[4] = tmp[4];
				}
				if (mid < right) {
					int[] r = query(i * 2 + 1, mid + 1, rr, Math.max(mid + 1, left), right);
					int leftLen = (mid - lr + 1);
					int rightLen = (rr - mid);
					
					if(ret[1] == 0)
						ret[4] = Math.max(ret[4], ret[0] + r[2] + r[3]);
					if(r[2] == 0)
						ret[4] = Math.max(ret[4], ret[0] + ret[1] + r[3]);
					ret[4] = Math.max(ret[4], r[4]);
					
					if(r[1] == rightLen) {
						ret[1] = ret[1] + r[1];
						ret[0] = ret[0];
					} else if(r[0] + r[1] == rightLen) {
						long tmp1 = ret[1];
						long tmp0 = ret[0];
						ret[1] = r[1];
						ret[0] = r[0];
						if(tmp1 == 0)
							ret[0] += tmp0;
					} else {
						ret[1] = r[1];
						ret[0] = r[0];
					}
					
					if(leftLen <= 0) {
						ret[2] = r[2];
						ret[3] = r[3];
					} else {
						if(ret[2] == leftLen) {
							ret[2] = ret[2] + r[2];
							ret[3] = r[3];
						} else if(ret[2] + ret[3] == leftLen) {
							if(r[2] == 0)
								ret[3] += r[3];
						} else {
							
						}
					}
					
					ret[4] = Math.max(ret[4], ret[0] + ret[1]);
					ret[4] = Math.max(ret[4], ret[2] + ret[3]);
					
				}
				return ret;
			}
		}
	}
	
	static class SuperBIT {
		  long[] dataMul, dataAdd;
		  SuperBIT(int n) {
		    dataMul = new long[n];
		    dataAdd = new long[n];
		  }
		  void update(int left, int right, long val) {
		    internalUpdate(left, val, -val * (left-1));
		    internalUpdate(right, -val, val * right);
		  }
		  void internalUpdate(int at, long mul, long add) {
		    while (at < dataMul.length) {
		      dataMul[at] += mul;
		      dataAdd[at] += add;
		      at |= (at + 1);
		    }
		  }
		  long query(int at) {
		    long mul = 0;
		    long add = 0;
		    int start = at;
		    while(at >= 0) {
		      mul += dataMul[at];
		      add += dataAdd[at];
		      at = (at & (at + 1)) -1;
		    }
		    return mul * start + add;
		  }
		  long query(int left, int right) {
		    if (left > right) {
		      int temp = left;
		      left = right;
		      right = temp;
		    }
		    return query(right) - (left > 0 ? query(left-1) : 0);
		  }
		  long[] indices; // Used for compressed BIT
		  // Compressed BIT constructor
		  // A BIT that only stores the values that will be updated. 
		  // indices is a sorted array of all the unique indices 
		  // that would be used for this BIT.
		  public SuperBIT(long[] indices) {
		    this.indices = indices;
		    dataMul = new long[indices.length];
		    dataAdd = new long[indices.length];
		  }
		 
		  // Search for the index in the array. If the index was not found, 
		  // return the first index lower than the search index.
		  int binSearch(int ind) {
		    int low = 0;
		    int high = dataMul.length-1;
		    while(low < high) {
		      int mid = (low + high+1)/2;
		      if(indices[mid] == ind)
		        return mid;
		      else if(indices[mid] < ind) 
		        low = mid;
		      else if(indices[mid] > ind) 
		        high = mid-1;
		    }
		    if(indices[low] > ind)
		      --low;
		    return low;
		  }
		  
		  // Read the largest index less than or equal to the given index.
		  long queryCompr(int index) {
		    return query(binSearch(index));
		  }
		  long queryCompr(int left, int right) {
		    return query(binSearch(left), binSearch(right));
		  }
		  // Update a specific index by a value. If the index is not in this 
		  // compressed BIT, the index below will be updated.
		  void updateCompr(int index, long val) {
		    int ind = binSearch(index);
		    update(ind, ind, val);
		  }
		  void updateCompr(int left, int right, long val) {
		    update(binSearch(left), binSearch(right), val);
		  } 
		}
	
	static class FastScanner {
	    BufferedReader br;
	    StringTokenizer st;
		
	    public FastScanner(InputStream i) {
	        br = new BufferedReader(new InputStreamReader(i));
	        st = new StringTokenizer("");
	    }
				
	    public String next() throws IOException {
	        if(st.hasMoreTokens())
	            return st.nextToken();
	        else
	            st = new StringTokenizer(br.readLine());
	        return next();
	    }

	    public int nextInt() throws IOException {
	        return Integer.parseInt(next());
	    }
	    public int[] nextIntArray(int n) throws IOException {
	    	int[] arr = new int[n];
	    	for(int i = 0; i < n; i++)
	    		arr[i] = nextInt();
	    	return arr;
	    }
	    public long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }
	    public long[] nextLongArray(int n) throws IOException {
	    	long[] arr = new long[n];
	    	for(int i = 0; i < n; i++)
	    		arr[i] = nextLong();
	    	return arr;
	    }
	    public double nextDouble() throws IOException {
	        return Double.parseDouble(next());
	    }
	    public double[] nextDoubleArray(int n) throws IOException {
	    	double[] arr = new double[n];
	    	for(int i = 0; i < n; i++)
	    		arr[i] = nextDouble();
	    	return arr;
	    }
	    public int[] nextOffsetIntArray(int n) throws IOException {
	    	int[] arr = new int[n];
	    	for(int i = 0; i < n; i++)
	    		arr[i] = nextInt() - 1;
	    	return arr;
	    }
	}
}
