Contest giao lưu lớp 10 các trường Chuyên (Lần 3)

Nhật có \(n\) lá bài, lá bài thứ \(i\) ghi một số nguyên dương \(a_i\). Anh trải các lá bài này thành một hàng ngang (lá bài thứ \(i\) nằm ở vị trí thứ \(i\) từ trái sang) và bắt đầu một thử thách nhỏ với chúng.

Nhật định nghĩa một đoạn các lá bài là một tập hợp các lá bài ở các vị trí liên tiếp nhau, có thể được mô tả bằng một cặp số \((l, r)\), với \(1 \le l \le r \le n\), với \(l\) là lá bài đầu tiên và \(r\) là lá bài cuối cùng của đoạn (hay nói cách khác, đoạn \((l, r)\) sẽ gồm các lá bài \(a_l, a_{l+1}, \dots, a_r\)). Nhật còn định nghĩa hai khái niệm liên quan đến đoạn các lá bài sau:

• Một đoạn được gọi là đẹp nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá \(k\) (nếu một phần không có lá bài nào thì tổng các số của phần đó là \(0\)).
• Một đoạn được gọi là hoàn hảo nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) có số lá bài bằng nhau sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá \(k\) (nếu một phần không có lá bài nào thì tổng các số của phần đó là \(0\)).

Ví dụ, trong dãy các lá bài \(a = 1, 2, 3, 3, 2, 1\) và \(k = 5\) ta có các trường hợp ví dụ sau:

• \((1, 2, 2, 1)\) không phải là một đoạn của dãy (vì đây không phải là đoạn gồm các lá bài liên tiếp).
• \((1, 2, 3)\) là một đoạn đẹp vì có thể chia đoạn này thành hai phần \((1, 2)\) và \((3)\) cùng có tổng các số bằng \(3\). Đây không phải là một đoạn hoàn hảo vì không thể được chia thành hai phần có số lá bài bằng nhau.
• \((2, 3, 3, 2)\) là một đoạn hoàn hảo vì có thể chia đoạn này thành hai phần \((2, 3)\) và \((3, 2)\) cùng có hai lá bài và có tổng các số ghi trên các lá bài bằng \(5\). Tương tự, \((3, 3)\) cũng là một đoạn hoàn hảo. Các đoạn \((2, 3, 3, 2)\) và \((3, 3)\) đồng thời cũng là các đoạn đẹp.
• \((1, 2, 3, 3, 2, 1)\) không phải là một đoạn đẹp vì không tồn tại cách chia nào thỏa mãn.

Thử thách mà Nhật đặt ra cho chính mình như sau: Với mỗi vị trí \(i\) mà \(1 \le i \le n\), anh phải tìm ra đoạn đẹp dài nhất và đoạn hoàn hảo dài nhất bắt đầu từ vị trí này. Độ dài của một đoạn là số lá bài nằm trong đoạn đó.

Nhật đã hoàn thành thử thách nhưng cần phải kiểm tra xem đáp án của mình có đúng hay không. Các bạn hãy viết một chương trình để giúp Nhật kiểm tra kết quả của mình nhé.

Input

• Dữ liệu vào từ tệp văn bản BEAUTY.inp:
  • Dòng đầu tiên gồm ba số nguyên dương \(n, k, \theta\) (\(1 \le n \le 10^6\), \(1 \le k \le 10^{15}\), \(1 \le \theta \le 2\)).
    • Nếu \(\theta = 1\), bạn cần phải xác định đoạn đẹp dài nhất bắt đầu từ mỗi vị trí \(i\) với \(1 \le i \le n\).
    • Nếu \(\theta = 2\), bạn cần phải xác định đoạn hoàn hảo dài nhất bắt đầu từ mỗi vị trí \(i\) với \(1 \le i \le n\).
  • Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• Ghi ra tệp văn bản BEAUTY.out:
  • Một dòng duy nhất gồm \(n\) số nguyên không âm:
    • Nếu \(\theta = 1\), số nguyên thứ \(i\) là độ dài đoạn đẹp dài nhất bắt đầu từ vị trí thứ \(i\), hoặc bằng \(0\) nếu không thể tìm được đoạn đẹp nào.
    • Nếu \(\theta = 2\), số nguyên thứ \(i\) là độ dài đoạn hoàn hảo dài nhất bắt đầu từ vị trí thứ \(i\), hoặc bằng \(0\) nếu không thể tìm được đoạn hoàn hảo nào.

Example

5 20 1
3 5 7 9 20

4 3 3 2 1

5 20 2
3 5 7 9 20

4 2 2 2 0

Scoring

• \(20\%\) số điểm có \(n \le 200\).
• \(20\%\) số điểm khác có \(n \le 5000\) và \(\theta = 1\).
• \(20\%\) số điểm khác có \(n \le 5000\) và \(\theta = 2\).
• \(20\%\) số điểm khác có \(\theta = 1\).
• \(20\%\) số điểm còn lại có \(\theta = 2\).

Cho một dãy số nguyên \(A_1, A_2, \dots, A_n\). Một đoạn con liên tiếp của \(A\) từ \(L\) đến \(R\), gọi là đoạn \([L, R]\) và gồm các phần tử \(A_L, A_{L+1}, \dots, A_R\), được gọi là hoàn hảo nếu:

• Tất cả các phần tử trong đoạn đôi một phân biệt, hay nói cách khác \(A_i \neq A_j\) với mọi \(L \le i < j \le R\).
• Chênh lệch giữa hai phần tử bất kỳ trong đoạn không vượt quá \(k\), hay nói cách khác, \(|A_i - A_j| \le k\) với mọi \(L \le i < j \le R\).

Bạn hãy tìm \(m\) đoạn con liên tiếp không giao nhau của \(A\) sao cho tất cả các đoạn con đều hoàn hảo và tổng độ dài của chúng là lớn nhất.

Hai đoạn con \((L_1, R_1)\) và \((L_2, R_2)\) được tính là giao nhau nếu chúng có chung ít nhất một phần tử. Độ dài của đoạn con \((L, R)\) là \(R - L + 1\).

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, k, m\) (\(1 \le n \le 5 \times 10^5\), \(1 \le k \le 10^9\), \(1 \le m \le 20\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

• Một dòng duy nhất gồm tổng độ dài lớn nhất tìm được.

Example

8 3 2
1 5 2 3 5 1 2 4

6

Scoring

• \(6\%\) số điểm có \(m = 1\) và \(n \le 80\).
• \(8\%\) số điểm khác có \(m = 1\) và \(n \le 200\).
• \(8\%\) số điểm khác có \(m = 1\) và \(n \le 2000\).
• \(9\%\) số điểm khác có \(m = 1\) và \(k = 10^9\).
• \(9\%\) số điểm khác có \(m = 1\).
• \(10\%\) số điểm khác có \(m = 2\) và \(n \le 2000\).
• \(11\%\) số điểm khác có \(m = 2\).
• \(11\%\) số điểm khác có \(m = 3\) và \(n \le 2000\).
• \(14\%\) số điểm khác có \(n \le 2000\).
• \(14\%\) số điểm còn lại không có giới hạn gì thêm.

Trong một dãy \(x_1, x_2, \ldots, x_k\), số \(x_i\) được gọi là cực trị địa phương khi và chỉ khi \(x_{i-1} < x_i > x_{i+1}\) hoặc \(x_{i-1} > x_i < x_{i+1}\). Một dãy \(x\) được gọi là đẹp khi và chỉ khi dãy tồn tại ít nhất một cực trị địa phương.

Bạn được cho một dãy \(a_1, a_2, \ldots, a_n\). Hãy đếm số lượng dãy con (không nhất thiết liên tiếp) của dãy là dãy đẹp.

Input

• Dòng đầu tiên gồm một số nguyên dương \(3 \le n \le 2\cdot 10^5\).
• 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 10^9\)).

Output

• Một dòng duy nhất gồm số lượng dãy con của \(a\) là dãy đẹp. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(10^9 + 7\).

Scoring

• \(30\%\) số điểm có \(n \le 20\).
• \(30\%\) số điểm khác có \(a_i \le 2\).
• \(20\%\) số điểm khác có \(n \le 2000\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Example

4
1 3 2 4

3