Segment tree lazy 1

Cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là xử lý \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Loại 1: \(1 \; x \; y \; val\) — Tăng giá trị của các phần tử từ chỉ số \(x\) đến \(y\) thêm \(val\) đơn vị.
  \((1 \le x \le y \le n, 1 \le val \le 10^9)\)
• Loại 2: \(2 \; l \; r\) — In ra giá trị lớn nhất của các phần tử trong đoạn từ chỉ số \(l\) đến \(r\).
  \((1 \le l \le r \le n)\)

Với mỗi truy vấn loại 2, hãy in ra kết quả trên một dòng.

Input

• Dòng đầu chứa số nguyên \(n\) — số phần tử trong mảng \((1 \le n \le 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((|a_i| \le 10^9)\)
• Dòng thứ ba chứa số nguyên \(q\) — số truy vấn \((1 \le q \le 10^5)\)
• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng ở trên.

Output

• Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Sample Input 1

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

Sample Output 1

4
6
7