RMQ vòng tròn (Circular RMQ)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì một mảng vòng với cập nhật cộng trên đoạn vòng và truy vấn giá trị nhỏ nhất trên đoạn vòng.

Input

Dòng 1 chứa $n$. Dòng 2 chứa $a_0,\ldots,a_{n-1}$. Dòng 3 chứa $m$. Mỗi dòng thao tác có hai hoặc ba số.

• l r: hỏi minimum trên đoạn vòng từ $l$ đến $r$.
• l r v: cộng $v$ vào đoạn vòng từ $l$ đến $r$.

Nếu $l>r$, đoạn gồm $l,l+1,\ldots,n-1,0,1,\ldots,r$.

Output

In minimum cho mỗi dòng thao tác có đúng hai số.

Subtask

• 20 điểm: $n,m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $1\le n\le2\cdot10^5$, $0\le m\le2\cdot10^5$, $|a_i|,|v|\le10^6$.

Ví dụ

Input

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

Output

1
0
0

Giải thích

Đoạn vòng từ 3 đến 0 gồm các vị trí 3 và 0, minimum ban đầu là 1. Sau khi cộng $-1$ lên đúng đoạn đó, truy vấn $[0,1]$ và đoạn vòng $[2,1]$ đều có minimum bằng 0.