BOI 2025 - Ngày 2

Bạn phụ trách phát triển các khu đất mới ở ngoại ô Toruń. Bạn đã quyết định xây dựng một con đường chính với \(n\) khu đất dọc theo đường, được đánh số từ \(1\) đến \(n\). Địa hình nơi đây hơi đồi núi, và độ cao của khu đất thứ \(i\) là \(a_i\) xentimét.

Hóa ra không ai muốn mua một khu đất nằm trên đoạn dốc. Cụ thể, với dãy độ cao \(a_1,a_2,\ldots,a_n\), một đoạn dốc là một dãy con liên tiếp \(a_{i-1},a_i,\ldots,a_j,a_{j+1}\) với \(2\le i\le j\le n-1\), thỏa mãn một trong hai điều kiện:

hoặc

Nói cách khác, đây là một đoạn gồm các khu đất ở vị trí \(i-1,i,\ldots,j,j+1\), trong đó mọi khu đất từ vị trí \(i\) đến vị trí \(j\) đều có cùng độ cao \(h\), và \(h\) lớn hơn độ cao ở một đầu, đồng thời nhỏ hơn độ cao ở đầu còn lại.

Bạn có thể tăng hoặc giảm độ cao của mỗi khu đất một lượng nguyên tùy ý, nhưng muốn tổng lượng thay đổi là nhỏ nhất. Hãy xác định tổng lượng thay đổi độ cao nhỏ nhất để không còn đoạn dốc nào. Tức là, cần tìm một dãy độ cao \(b_1,b_2,\ldots,b_n\) không có đoạn dốc sao cho giá trị sau nhỏ nhất:

Các độ cao \(b_i\) phải là số nguyên, không nhất thiết phải dương, và không chịu bất kỳ ràng buộc nào khác.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số khu đất dọc theo con đường.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là độ cao ban đầu của khu đất thứ \(i\).

Dữ liệu ra

In ra tổng lượng thay đổi độ cao nhỏ nhất để không còn đoạn dốc nào.

Ràng buộc

• \(1\le n\le 2\cdot 10^5\).
• \(0\le a_i\le 10^9\) với mọi \(1\le i\le n\).

Phân nhóm

1. \(4\) điểm: \(n\le 5\) và \(a_i\le 10\) với mọi \(1\le i\le n\).
2. \(13\) điểm: \(n\le 2000\).
3. \(8\) điểm: \(a_i\le 10\) với mọi \(1\le i\le n\).
4. \(19\) điểm: \(a_i<a_{i+1}\) với mọi \(1\le i<n\).
5. \(29\) điểm: \(n\le 2\cdot 10^4\).
6. \(27\) điểm: không có ràng buộc bổ sung.

Ví dụ

11
7 2 1 2 5 7 8 8 10 8 8

5

Nhà bác học nổi tiếng Nicolaus Copernicus sinh ra và lớn lên ở Toruń vào thế kỷ XV. Gần đây, các nhà khảo cổ đã tìm thấy cuốn sổ ghi chép của ông và biết được rằng ông thích dùng các lũy thừa của \(2\) để lưu trữ những số lớn. Ngay cả khi cộng hai lũy thừa của \(2\):

Copernicus cũng tính tổng rồi làm tròn lên đến lũy thừa của \(2\) gần nhất. Nói cách khác, ông tính \(2^a+2^b\) thành \(2^{\max(a,b)+1}\).

Để tính một biểu thức dài hơn có dạng

trước tiên, ông thêm các dấu ngoặc để được một biểu thức có cách đặt ngoặc hợp lệ. Một biểu thức như vậy được định nghĩa như sau: \(2^a\) là một biểu thức có cách đặt ngoặc hợp lệ với mọi số nguyên không âm \(a\); nếu \(E_1\) và \(E_2\) có cách đặt ngoặc hợp lệ thì \((E_1+E_2)\) cũng vậy. Không có biểu thức nào khác được coi là có cách đặt ngoặc hợp lệ.

Chẳng hạn, có thể thêm dấu ngoặc vào biểu thức \(2^5+2^4+2^4+2^4+2^5\) để được

Sau đó, ông tính giá trị của biểu thức đã đặt ngoặc bằng cách thực hiện từng phép cộng theo quy tắc trên. Kết quả có thể khác nhau tùy theo cách đặt ngoặc. Ví dụ, dưới đây là hai cách tính biểu thức \(2^5+2^4+2^4+2^4+2^5\):

Trang đầu tiên trong cuốn sổ của Copernicus chỉ chứa một biểu thức, được gọi là biểu thức chính:

Những trang sau nhắc đến các đoạn của biểu thức chính, có dạng

với \(1\le\ell\le r\le n\).

Bạn chưa rõ ý nghĩa của những đoạn này, nhưng đoán rằng với mỗi đoạn, bạn cần tìm kết quả nhỏ nhất có thể nhận được bằng cách đặt ngoặc và tính toán theo quy tắc trên. Mỗi đoạn được xét độc lập với các đoạn khác.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\), lần lượt là số số hạng trong biểu thức chính và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số mũ của lũy thừa của \(2\) thứ \(i\) trong biểu thức chính.

\(q\) dòng tiếp theo mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(\ell\) và \(r\), chỉ đoạn bắt đầu ở lũy thừa của \(2\) thứ \(\ell\) và kết thúc ở lũy thừa của \(2\) thứ \(r\) trong biểu thức chính.

Dữ liệu ra

In ra \(q\) dòng. Dòng thứ \(i\) chứa số mũ của lũy thừa của \(2\) nhỏ nhất có thể nhận được khi tính đoạn trong truy vấn thứ \(i\) theo quy tắc đã mô tả. Chỉ in số mũ, không in giá trị của lũy thừa.

Ràng buộc

• \(1\le n,q\le 300\,000\).
• \(0\le a_i\le 10^6\) với mọi \(1\le i\le n\).
• \(1\le\ell\le r\le n\) trong mỗi truy vấn.

Phân nhóm

1. \(6\) điểm: \(n\le 8\) và \(q\le 10\).
2. \(8\) điểm: \(n\le 200\).
3. \(23\) điểm: \(n,q\le 2000\).
4. \(22\) điểm: \(a_i\le 20\) với mọi \(1\le i\le n\).
5. \(41\) điểm: không có ràng buộc bổ sung.

Ví dụ

8 4
2 4 2 5 4 4 4 5
4 8
1 4
2 5
1 7

7
7
7
8

Từ thời Trung cổ, Toruń đã nổi tiếng với món bánh gừng truyền thống. Cậu bé Nicolaus muốn mua \(n\) hộp bánh gừng tại cửa hàng yêu thích của mình. Tuy nhiên, cửa hàng có những quy định rất nghiêm ngặt: ban đầu, Nicolaus nhận \(n\) hộp đã có sẵn bánh, trong đó hộp thứ \(i\) chứa \(a_i\) chiếc. Sau đó, cậu có thể mua thêm bánh và cho vào một số hộp sao cho ước chung lớn nhất của số bánh trong tất cả các hộp bằng \(1\). Có thể chứng minh rằng điều này luôn thực hiện được.

Ước chung lớn nhất của nhiều số là số nguyên dương lớn nhất mà tất cả các số đó đều chia hết cho nó.

Hãy giúp Nicolaus tính tổng số bánh ít nhất cần thêm vào các hộp để ước chung lớn nhất của số bánh trong tất cả các hộp bằng \(1\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số hộp bánh.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số bánh ban đầu trong hộp thứ \(i\).

Dữ liệu ra

In ra một dòng chứa một số nguyên là tổng số bánh ít nhất Nicolaus cần thêm vào các hộp. Nếu không cần thêm bánh mà ước chung lớn nhất của các số đã bằng \(1\), in ra \(0\).

Ràng buộc

• \(2\le n\le 10^6\).
• \(1\le a_i\le 10^7\) với mọi \(1\le i\le n\).

Phân nhóm

1. \(17\) điểm: \(n=2\).
2. \(34\) điểm: \(n\le 10\).
3. \(11\) điểm: \(n\le 1000\).
4. \(38\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
90 84 140

2