Nông dân John muốn chia đều cỏ giữa hai con bò yêu thích của mình là Bessie và Elsie. Anh có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) bó cỏ được sắp xếp theo thứ tự không tăng dần, trong đó bó cỏ thứ \(i\) có \(a_i\) cọng cỏ (\(2 \times 10^5 \geq a_1 \geq a_2 \geq ... \geq a_N \geq1\)).

Nông dân John đang nghĩ đến chuyện chia những bó cỏ một cách lần lượt cho hai con bò, cụ thể như sau:

• Nông dân John chia các bó cỏ theo đúng thứ tự từ \(l\) đến \(r\) trong kho cỏ cho trước.
• Với bó cỏ thứ \(i\), anh John sẽ đưa cho con bò có ít cỏ hơn. Nếu 2 con bò cố lượng cỏ bằng nhau, anh John sẽ đưa cho Bessie.

Bạn được cho Q truy vấn (\(1 \leq Q \leq 2 \times 10^5\)), mỗi truy vấn gồm 3 số nguyên \(l, r, x\) (\(1 \leq l \leq r \leq N, |x| \leq 10^9\)). Với mỗi truy vấn, bạn cần tìm xem Bessie sẽ có nhiều hơn Elsie bao nhiêu cọng cỏ, biết Bessie ban đầu có nhiều hơn Elsie \(x\) cọng cỏ. Lưu ý rằng giá trị này âm nếu Elsie có nhiều cỏ hơn Bessie.

Input

• Dòng đầu tiên chứa \(N\).
• Dòng thứ hai chứa \(a_1…a_N\).
• Dòng thứ ba chứa \(Q\).
• \(Q\) dòng tiếp theo chứa \(l, r, x\).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi truy vấn.

Scoring

• Subtask \(1\): \(Q \leq 100\)
• Subtask \(2\): Tối đa \(100\) giá trị \(a_i\) khác nhau
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

16
12
7
4
1
2
1