Bài tập

Có thể nhận thấy ở thời điểm hiện tại, ngành công nghiệp game Esport ngày càng phát triển. Khi nói đến tựa game Esport nổi tiếng và hấp dẫn nhất, không thể thiếu Liên Minh Huyền Thoại (League of Legends). Với mức độ phủ sóng khủng khiếp trên toàn cầu nên các giải đấu về trò chơi này luôn nhận được sự quan tâm của đông đảo người hâm mộ. Và giải đấu LCK cũng là một trong số đó.

LCK là viết tắt của League of Legends Champions Korea, trước đây được biết đến với tên Ongamenet LCK (OGN) và được tổ chức bởi 1Ongamenet, là đấu trường cao nhất của bộ môn thể thao điện tử Liên Minh Huyền Thoại tại Hàn Quốc". Hiện tại, LCK mùa hè \(2023\) đã chính thức khép lại với chiến thắng không thể bàn cãi của GenG.

Fekar - một trong những tuyển thủ huyền thoại của làng Liên Minh Huyền Thoại, sau một thời gian dài gắn bó đã giải nghệ. Fekar đã được đề cử lên làm trưởng ban tổ chức của giải đấu LCK. Vì một lí do nào đó, Fekar đã thay đổi cơ cấu của giải đấu này như sau:

Trước khi bắt đầu mùa giải, mỗi tuyển thủ đều sẽ có một huy hiệu hiển thị một số nguyên \(h_{i}\) - đại diện cho chỉ số kĩ năng của tuyển thủ đó (với \(i\) là số hiệu của tuyển thủ, có tất cả \(n\) tuyển thủ tham gia thi đấu). Thay vì thi đấu theo đội tuyển của mình với hình thức \(5\) vs \(5\), Fekar đã thay đổi luật, tất cả các tuyển thủ sẽ không theo một đội tuyển nào, xếp các tuyển thủ từ trái sang phải theo thứ tự từ \(1\) đến \(n\), sau đó sẽ chia lại các đội tuyển thi đấu (đồng nghĩa rằng bạn sẽ không biết đồng đội của bạn là ai). Fekar yêu cầu các tuyển thủ thuộc cùng một đội tuyển phải đứng sát nhau, một tuyển thủ phải thuộc chính xác một đội tuyển. Nói cách khác, một đội tuyển thi đấu sẽ là một đoạn con trên dãy các tuyển thủ. Quy định này sẽ không hạn chế người của một đội tuyển.

Fekar quy định sức mạnh của một đội tuyển là sự chênh lệnh giữa tuyển thủ có chỉ số kĩ năng cao nhất và tuyển thủ có chỉ số kĩ năng thấp nhất. Nói một cách "công thức" hơn,
nếu tuyển thủ đầu tiên của đội tuyển \(X\) có số thứ tự là \(i\), và tuyển thủ cuối cùng có số thứ tự là \(j\) \((1 \leq i \leq j \leq n)\), sức mạnh đội tuyển là giá trị \(max(h_{i}...h_{j}) - min(h_{i}...h_{j})\).

Gọi sức mạnh tổng thể của giải đấu là tổng sức mạnh của các đội tuyển, Fekar muốn giá trị này đạt càng lớn càng tốt, các bạn hãy giúp Fekar chia đội tuyển một cách hợp lí nhé!

Input

Dòng đầu tiên là số nguyên \(n\) - số tuyển thủ thi đấu \((2 \leq n \leq 10^6)\).

Dòng tiếp theo là \(n\) số nguyên \(h_{1}, h_{2}, h_{3}, ..., h_{n}\) \((-10^9 \leq h_{i} \leq 10^9)\).

Output

Kết quả bài toán.

Example

5
1 2 3 1 2

3

Scoring

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\).

\(20\%\) số test tương ứng với \(20\%\) số điểm, \(h_{i} <= h_{i + 1}\) \((1 \leq i < n)\).

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).

\(20\%\) số test tương ứng với \(20\%\) số test, \(h_{i} = a\) hoặc \(h_{i} = b\) với \(a, b\) là hằng số.

\(20\%\) số test còn lại không có ràng buộc gì thêm.

Giáo sư 3M vừa mới phát hiện ra sinh vật mới chưa từng xuất hiện trước đây. Sinh vật này rất
kì lạ khi có thể thay đổi mã gen của mình. Mã gen của sinh vật được biển diễn dưới dạng một
dãy các phần tử số nguyên. Được biết trong vòng đời của sinh vật có thể biến đổi duy nhất \(1\)
lần trong đoạn gen từ \(L\) đến \(R\) bằng cách thay đổi các số nguyên trong trên dãy thành \(a_L\).
Giáo sư muốn biết với mã gen đã cho sinh vật này có thể biến đổi thành bao nhiêu mã gen
khác nhau. Các bạn hãy giúp giáo sư 3M nhé.

Input

Vào từ file văn bản GCC.INP:

• Dòng đầu ghi số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ \(2\) ghi \(n\) số nguyên \(a_i\) \((1 \leq |a_i| \leq 10^6)\).

Output

Ghi ra file văn bản GCC.OUT:

• Gồm một số nguyên dương duy nhất là số mã gen khác nhau có thể.

Example

4 1
1 2 3

4

Scoring

• \(10\%\) số test tương ứng với \(10\%\) số điểm của \(n \leq 500\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10^3\), \(1 \leq a_i \leq 9\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có các phần tử \(a_i\) phân biệt.
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm

GSFOS chuẩn bị thám hiểm một pháo đài cổ. Pháo đài có \(n\) phòng, nối liên thông với nhau bằng \(n-1\) đường hầm. Đường hầm thứ \(i\) nối hai phòng \(u_i\) và \(v_i\) với nhau và có độ dài \(w_i\).

Để lên kế hoạch thám hiểm, GSFOS cần chọn một đường đi nối hai phòng \(u\) và \(v\) bất kỳ. Gọi tập các đỉnh trên đường này là
\(S=\{u,x_1,x_2,\dots,x_k,v\}\),
theo thứ tự sao cho có cạnh nối lần lượt \(u\text{--}x_1\text{--}x_2\text{--}\dots\text{--}x_k\text{--}v\). Độ dài của đường đi từ \(u\) tới \(v\) được ký hiệu là \(\operatorname{value}(u,v)\).

Sau khi chọn đường \(S\), GSFOS chọn một phòng \(y\) không thuộc \(S\). Định nghĩa

trong đó \(\operatorname{dist}(y,z)\) là khoảng cách giữa hai phòng \(y\) và \(z\). Nếu không tồn tại phòng \(y\) phù hợp (tức mọi phòng đều thuộc \(S\)) thì ta lấy \(\operatorname{distance}(y,S)=0\). Nếu không thể chọn được hai phòng \(u,v\) để tạo thành đường đi thì \(\operatorname{value}(u,v)=0\).

Giá trị của cách chọn là

Hãy tính giá trị lớn nhất có thể đạt được khi tối ưu hóa cả đường \(S\) (tức chọn \(u,v\)) và phòng \(y\).

Input

• Dòng đầu chứa một số nguyên dương \(n\) (\(1\le n \le 3\cdot 10^5\)) --- số phòng trong pháo đài.
• \(n-1\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u, v, w\) (\(1\le u,v\le n\), \(1\le w\le 10^3\)) --- có một đường hầm giữa phòng \(u\) và \(v\) với độ dài \(w\).

Output

• In ra một số nguyên duy nhất --- giá trị lớn nhất của \(\operatorname{value}(u,v)\times \operatorname{distance}(y,S)\) có thể đạt được.

Example

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

15

Scoring

• Subtask 1 (15%): \(n \le 100\).
• Subtask 2 (20%): \(n \le 3000\).
• Subtask 3 (30%): Mỗi phòng có tối đa \(3\) đường hầm kề.
• Subtask 4 (35%): Không có ràng buộc gì thêm.

Cho dãy số \(a\) gồm \(n\) số nguyên đánh số từ \(1\) đến \(n\). Ban đầu dãy \(a\) gồm toàn số \(0\). Cho \(q\) truy vấn, mỗi truy vấn được cho dưới dạng hai số nguyên \(i\) và \(k\) : tăng \(a_{i}\) lên \(k\) đơn vị, \(a_{i+1}\) lên \(k - 1\) đơn vị,... \(a_{i+k−1}\) lên \(1\) đơn vị.

Hãy in ra dãy \(a\) sau khi thực hiện \(q\) truy vấn này.

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \((n, q \leq 5 \times 10^5)\).

\(q\) dòng tiếp theo, mỗi dòng tương ứng với một truy vấn là hai số nguyên \(i\) và \(k\) \((1 \leq i \leq n; 1 \leq k \leq n-i+1)\).

Output

Một dòng duy nhất là dãy \(a_{1},a_{2},...,a_{n}\) sau khi thực hiện xong \(q\) truy vấn.

Example

7 5
5 2
1 6
1 6
7 1
7 1

12 10 8 6 6 3 2 

Scoring

\(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 1000\).

\(30\%\) số test tương ứng với \(30\%\) số điểm mọi \(k\) trong \(q\) truy vấn bằng nhau.

\(40\%\) số test tương ứng với \(30\%\) số điểm còn lại không có ràng buộc gì thêm.