Bài tập

Trên hòn đảo hình vòng tròn, có \(n\) chiếc rương báu vật xếp thành một vòng. Mỗi chiếc rương được đánh số từ \(0\) đến \(n - 1\) và chứa một số lượng vàng ban đầu là \(a_0, a_1, \ldots, a_{n-1}\).

Cướp biển Lập trình viên rất quan tâm đến giá trị của kho báu và thường xuyên thực hiện các hành động sau:

• inc(lf, rg, v) --- Thêm \(v\) thỏi vàng vào mỗi chiếc rương từ vị trí \(lf\) đến \(rg\) (tính cả hai đầu).
• rmq(lf, rg) --- Truy xuất thông tin: rương nào có ít vàng nhất trong đoạn từ \(lf\) đến \(rg\)?

Vì các rương được xếp thành vòng tròn, nên đoạn từ \(lf\) đến \(rg\) có thể được hiểu như sau:

• Nếu \(lf \le rg\): đoạn gồm các chỉ số từ \(lf\) đến \(rg\).
• Nếu \(lf > rg\): đoạn gồm các chỉ số từ \(lf\) đến \(n - 1\), rồi tiếp tục từ \(0\) đến \(rg\).

Hãy giúp Lập trình viên thực hiện tuần tự các thao tác, và ghi lại kết quả mỗi lần anh ta truy vấn rmq!

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng rương.
• Dòng thứ hai chứa \(n\) số nguyên \(a_0, a_1, \ldots, a_{n-1}\) \((-10^6 \le a_i \le 10^6)\) --- số lượng vàng ban đầu ở mỗi rương.
• Dòng thứ ba chứa số nguyên \(m\) \((0 \le m \le 2 \cdot 10^5)\) --- số truy vấn.

• \(m\) dòng tiếp theo, mỗi dòng chứa một truy vấn, có thể ở một trong hai dạng:

• lf rg --- Truy vấn loại rmq.

• lf rg v --- Truy vấn loại inc.

Output

Với mỗi truy vấn loại rmq, in ra một dòng chứa số lượng vàng ít nhất trong đoạn được hỏi.

Example

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

1
0
0

Cho một cây có \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Mỗi đỉnh có một giá trị ban đầu.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• Thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \cdot 10^5)\) -- số đỉnh của cây và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) \((1 \leq v_i \leq 10^9)\) -- giá trị của mỗi đỉnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).

• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có một trong hai dạng sau:

• 1 s x: Thay đổi giá trị của đỉnh \(s\) thành \(x\) \((1 \leq s \leq n, 1 \leq x \leq 10^9)\).

• 2 a b: Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\) \((1 \leq a, b \leq n)\).

Output

• In ra \(Q\) số nguyên trên một dòng duy nhất biểu thị giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Example

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

4 3 

Trên trục số, Roy và Biv có một tập hợp gồm \(n\) điểm, mỗi điểm có vị trí và màu sắc. Mỗi điểm là một trong ba màu: đỏ (R), xanh lá (G) hoặc xanh dương (B).

Họ muốn nối các điểm lại bằng những đoạn thẳng (cạnh). Mỗi cạnh có thể nối hai điểm bất kỳ, và chi phí của cạnh chính là khoảng cách giữa hai điểm được nối.

Mục tiêu là chọn một số cạnh sao cho toàn bộ \(n\) điểm được kết nối (trực tiếp hoặc gián tiếp). Tuy nhiên, có một điều đặc biệt:

• Roy không nhìn thấy màu đỏ.
• Biv không nhìn thấy màu xanh dương.

Do đó, họ muốn chọn các cạnh sao cho:

• Nếu bỏ toàn bộ điểm màu đỏ, thì các điểm còn lại (xanh lá và xanh dương) vẫn phải kết nối được với nhau.
• Nếu bỏ toàn bộ điểm màu xanh dương, thì các điểm còn lại (xanh lá và đỏ) cũng phải kết nối được với nhau.

Hãy giúp họ tìm cách kết nối các điểm với tổng chi phí nhỏ nhất, thoả mãn hai điều kiện trên.

Chú ý: Tọa độ các điểm là phân biệt và tăng dần.

Hai điểm được xem là "kết nối với nhau" nếu tồn tại chuỗi các cạnh nối giữa chúng.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 300\,000\)) --- số lượng điểm.
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(p_i\) (\(1 \le p_i \le 10^9\)) và một ký tự \(c_i\) (\(c_i \in \{R, G, B\}\)) --- tọa độ và màu sắc của điểm thứ \(i\).
• Các tọa độ \(p_i\) là phân biệt và tăng dần.

\OutputFile

In ra chi phí nhỏ nhất cần thiết để kết nối các điểm, thỏa mãn điều kiện của Roy và Biv.

\Scoring

• Subtask 1 (10 điểm): tất cả các điểm chỉ có màu G.
• Subtask 2 (11 điểm): không có điểm nào có màu G.
• Subtask 3 (15 điểm): tất cả các điểm có màu R hoặc màu G.
• Subtask 4 (17 điểm): \(n \le 10\).
• Subtask 5 (47 điểm): không có ràng buộc gì thêm.

Example

4
1 G
4 R
8 B
15 G

24

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử.

Với mỗi đoạn con \(A[l..r]\) (\(1 \le l \le r \le n\)), ta định nghĩa:

• \(W(l,r,x)\) là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\dots,A[r]\).

• Gọi \(B\) là dãy gồm các phần tử đoạn \(A[l..r]\), và sắp xếp \(B\) tăng dần được dãy \(C\).

  Tập trung vị của đoạn là:
  $
  S(l,r) = { C[\lfloor (k-1)/2 \rfloor],\; C[\lceil (k-1)/2 \rceil] },
  $
  trong đó \(k = r-l+1\).

Giá trị của đoạn \((l,r)\) được định nghĩa là:
$
\max_{x \in S(l,r)} W(l,r,x).
$

Lưu ý: tập \(S(l,r)\) sẽ chứa phần tử trung vị duy nhất nếu đoạn có số phần tử lẻ, và chứa hai phần tử trung vị nếu đoạn có số phần tử chẵn.

Yêu cầu: Tìm giá trị lớn nhất trong tất cả các đoạn \((l,r)\).

\InputFile

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le n\)).

\OutputFile

In ra một số nguyên duy nhất --- giá trị lớn nhất có thể đạt được.

\Scoring

• \(11\) điểm: \(n \le 100\).
• \(17\) điểm: \(n \le 2 \times 10^3\).
• \(7\) điểm: tồn tại \(x\) sao cho dãy tăng đến \(x\) rồi giảm sau đó.
• \(12\) điểm: \(A_i \le 3\).
• \(13\) điểm: mỗi giá trị xuất hiện nhiều nhất 2 lần.
• \(22\) điểm: \(n \le 8 \times 10^4\).
• \(18\) điểm: không có ràng buộc thêm.

Example

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2