THTB 2026 An Hải - Thanh Khê - Sơn Trà

An vẽ một hình chữ nhật lên giấy và yêu cầu Bình đoán chu vi của hình chữ nhật mà An vừa vẽ. Tuy nhiên, An chỉ nói cho Bình biết hình chữ nhật có diện tích bằng \(s\) và các kích thước (chiều dài và chiều rộng) của nó là các số nguyên dương.

Bình đoán rằng An sẽ vẽ hình có chu vi nhỏ nhất hoặc lớn nhất trong số các hình chữ nhật thỏa mãn cả hai điều kiện mà An đã đưa ra, nên muốn nhờ bạn tính chu vi của hình được An vẽ trong hai trường hợp này. Các bạn hãy tính toán giúp Bình nhé.

Input

• Một dòng duy nhất gồm một số nguyên dương \(s\) (\(1 \le s \le 10^{12}\)).

Output

• Một dòng duy nhất gồm hai số nguyên dương, lần lượt là chu vi nhỏ nhất và lớn nhất có thể của hình chữ nhật mà An đã vẽ.

Example

6

10 14

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(s \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(s \le 10^6\).
• Subtask \(3\) (\(30\%\) số điểm): Không có giới hạn gì thêm.

Chấm điểm:

• Nếu bạn đưa ra đúng một trong hai số trong một test, bạn được \(60\%\) số điểm cho test đó.
• Nếu bạn đưa ra đúng cả hai số trong một test, bạn được \(100\%\) số điểm cho test đó.

Hôm nay thầy Thành cho các bạn trong đội tuyển làm một bài kiểm tra về chủ đề phép chia hết. Thầy sẽ đưa cho mỗi bạn một số nguyên dương, và yêu cầu các bạn tính số lượng ước của số được đưa ra.

Do thầy Thành rất lười tạo ra các số nguyên dương khác nhau, thầy chỉ tạo ra một dãy số nguyên dương \(a\) gồm \(n\) phần tử \(a_1, a_2, a_3, \ldots, a_n\). Sau đó, với mỗi học sinh, thầy chọn ra một bộ ba chỉ số \((u, v, w)\) với \(1 \le u \le v < w \le n\), rồi tính các tổng \(s(u, v) = a_u + a_{u+1} + \ldots + a_v\), \(s(u, w) = a_u + a_{u+1} + \ldots + a_w\) và lấy kết quả \(x\) của phép tính \(x = s(u, w) - s(u, v)\) làm đề bài. Rất may, số học sinh của đội tuyển lại đúng bằng số lượng bộ chỉ số có thể chọn, nên thầy có thể chọn các bộ \((u, v, w)\) sao cho mỗi bạn đều có thể nhận được kết quả \(x\) từ các bộ chỉ số khác nhau (mặc dù có thể số nguyên dương mà các bạn nhận được là giống nhau).

Thầy Thành không muốn kiểm tra kết quả của từng bạn, nên thầy có một giải pháp đơn giản: cộng kết quả của tất cả các bạn lại rồi đối chiếu với đáp án, nếu tổng kết quả của các bạn là chính xác, tất cả các bạn trong đội tuyển sẽ được \(10\) điểm, ngược lại thì tất cả các bạn sẽ được \(0\) điểm. Tuy nhiên việc tính toán chính xác đáp án cũng mất rất nhiều thời gian và dễ sai sót, nên các bạn hãy tính toán giúp thầy Thành nhé.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5000\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 5000\)).

Output

• Một dòng duy nhất gồm tổng cần tính.

Example

3
1 2 3

8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 400\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_i \le 500\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Phong là một học sinh rất say mê các hoạt động STEM và rất thích thực hiện những thí nghiệm thực tế. Trong một lần thí nghiệm, Phong đã đo nhiệt độ trung bình trong \(n\) ngày liên tiếp và được các kết quả là các số nguyên đôi một khác nhau.

Tiếp theo, Phong thực hiện các bước tách nhóm dữ liệu. Với mỗi bước, Phong sẽ tìm ngày có nhiệt độ cao nhất và ngày có nhiệt độ thấp nhất trong dãy, sau đó tách dữ liệu nhiệt độ của các ngày nằm trong đoạn giữa hai ngày này (kể cả hai ngày có nhiệt độ cao nhất và thấp nhất) thành một nhóm, và nối dữ liệu của các ngày còn lại thành một dãy mới (giữ nguyên thứ tự). Phong lặp lại quy trình này trên dãy mới cho đến khi dãy này trở thành dãy rỗng và đếm số nhóm đã tách được.

Phong thực hiện quy trình tách nhóm dữ liệu này với \(q\) bộ dữ liệu khác nhau, mỗi bộ dữ liệu là nhiệt độ trung bình của các ngày trong một đoạn liên tiếp từ ngày thứ \(l\) đến ngày thứ \(r\). Vì dữ liệu gồm rất nhiều ngày nên việc tính toán bằng tay có thể mất rất nhiều thời gian, Phong muốn nhờ bạn viết một chương trình tính nhanh số nhóm mà Phong tách được. Bạn hãy giúp Phong tính toán thông tin này nhé.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n \le 2 \cdot 10^5, 1 \le q \le 500\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 2 \cdot 10^5\)), các giá trị \(a_i\) đôi một khác nhau.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l, r\) (\(1 \le l \le r \le n\)).

Output

• Với mỗi bộ dữ liệu, in ra số nhóm mà Phong tách được.

Example

7 3
5 2 8 1 9 3 7
1 7
2 6
1 3

4
3
2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n = 2000, q = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(q = 1\), không có ràng buộc gì thêm về \(n\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.