Bài tập

Có \(n\) hộp quà, các hộp quà được đánh số từ \(1\) đến \(n\), hộp thứ \(i\) có giá trị \(a_i\) (\(1 \le a_i \le m\)). Lớp Nam được giao nhiệm vụ chuẩn bị \(K\) giỏ quà từ \(n\) hộp quà đã có, tuân thủ tất cả các quy tắc sau:

• Mỗi giỏ quà gồm hai hộp quà;
• Hộp quà thứ nhất được lấy từ các hộp quà có chỉ số từ \(1\) đến \(K\), hộp quà thứ hai được lấy từ các hộp quà có chỉ số từ \(K + 1\) đến \(n\);
• Giá trị hộp quà thứ nhất nhỏ hơn giá trị hộp quà thứ hai.

Ví dụ: Cho các hộp quà có giá trị: \(2\) \(1\) \(4\) \(2\) \(3\) \(2\) \(4\) \(5\) \(2\) \(3\) Nam có thể ghép được \(4\) hộp quà có giá trị \(2\) \(1\) \(4\) \(2\) với \(6\) hộp quà có giá trị \(3\) \(2\) \(4\) \(5\) \(2\) \(3\) tạo thành \(4\) giỏ quà được ghép là \(\{(2, 3), (1, 2), (4, 5), (2, 3)\}\) hoặc \(\{(2, 3), (1, 2), (4, 5), (2, 4)\}\).

Yêu cầu: Cho \(n\) hộp quà có giá trị \(a_1, a_2, a_3, ..., a_n\), hãy tìm \(K\) lớn nhất theo quy tắc trên.

Input

Vào từ tệp văn bản CAU3.INP có cấu trúc:

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) \((1 \leq n \leq 10^5, 1 \leq m \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le m\)).

Output

Ghi ra tệp văn bản CAU3.OUT là số \(K\) lớn nhất tìm được, nếu không có nghiệm thì in ra \(-1\).

Example

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

4

5 6
5 4 2 1 2

-1

Scoring

• Subtask \(1\) (\(2,0\) điểm): \(1 \leq n \leq 100, 1 \leq m \leq 10^3\).
• Subtask \(2\) (\(1,5\) điểm): \(100 \leq n \leq 5 \times 10^3, 1 \leq m \leq 10^9\)
• Subtask \(3\) (\(1,5\) điểm): không có ràng buộc gì thêm.

Mọi người đều đã quen thuộc với bài toán tìm LIS (Longest Increasing Subsequence) của một dãy số. Tuy nhiên, Ami lại có một sở thích hơi khác. Thay vì nghiên cứu một dãy số, cậu chỉ nhìn vào các chữ số của một số nguyên.

Ami định nghĩa LIDS (Longest Increasing Digit Subsequence) của một số nguyên là độ dài của dãy con tăng dài nhất được tạo bởi các chữ số của số đó.

Ví dụ:

• LIDS của \(1234\) có độ dài \(4\).
• LIDS của \(12234\) có độ dài \(4\).
• LIDS của \(456123\) có độ dài \(3\).

Một số ví dụ về dãy chữ số tăng hợp lệ là:

Trong khi đó,

không phải là dãy tăng.

Cho hai số nguyên \(L\) và \(R\).

Yêu cầu. Trong tất cả các số nguyên thuộc đoạn \([L,R]\):

• Tìm giá trị lớn nhất của LIDS.
• Đếm số cách tạo ra LIDS lớn nhất đó.

Hai cách được coi là khác nhau nếu:

• Hai dãy chữ số thu được khác nhau; hoặc
• Chúng được lấy từ các vị trí khác nhau trong cùng một số.

\InputFile

Dòng đầu chứa số nguyên \(T\) \((1 \le T \le 10^4)\) là số lượng bộ dữ liệu.

Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên

thỏa mãn

\OutputFile

Với mỗi bộ dữ liệu, in ra một dòng theo định dạng

\begincenter
Case x: a b
\endcenter

trong đó:

• \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\));
• \(a\) là độ dài lớn nhất của LIDS trong đoạn;
• \(b\) là số cách tạo ra LIDS có độ dài lớn nhất.

\Examples

\beginexample
\exmp
2
111 114
15432 15432

Case 1: 2 6
Case 2: 2 4

\endexample

\Note

Ở bộ dữ liệu thứ nhất:

• LIDS của \(111\) có độ dài \(1\).
• LIDS của \(112\), \(113\) và \(114\) đều có độ dài \(2\).

Do đó, độ dài LIDS lớn nhất là \(2\) và có tổng cộng \(6\) cách tạo ra các dãy con tăng có độ dài này.

Ở bộ dữ liệu thứ hai, số \(15432\) có LIDS bằng \(2\). Có bốn cách đạt được giá trị này:

\endproblem

Bạn có một dãy số nguyên gồm \(n\) phần tử. Trải qua thời gian, dãy số này liên tục thay đổi và bạn cần xử lý một loạt các truy vấn được đưa ra.

Có tổng cộng \(q\) truy vấn, mỗi truy vấn là một trong hai loại sau:

• Loại 1: 1 $k$ $u$ --- Cập nhật giá trị phần tử ở vị trí \(k\) thành \(u\).
• Loại 2: 2 $a$ $b$ --- Trong tất cả các đoạn con bắt đầu tại \(a\) và kết thúc tại \(i\) với \(a \le i \le b\), hãy tìm đoạn con có tổng lớn nhất.

Cụ thể hơn, với truy vấn loại 2, bạn cần xét các đoạn \([a, a], [a, a+1], \dots, [a, b]\) và chọn ra đoạn có tổng lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- độ dài ban đầu của dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) (\(-10^9 \le x_i \le 10^9\)) --- các phần tử ban đầu của dãy.

• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng:

• 1 $k$ $u$ --- cập nhật \(x_k \leftarrow u\), với \(1 \le k \le n\), \(-10^9 \le u \le 10^9\).

• 2 $a$ $b$ --- truy vấn tổng lớn nhất của một đoạn con bắt đầu tại \(a\) và kết thúc tại một vị trí bất kỳ trong đoạn \([a, b]\), với \(1 \le a \le b \le n\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tương ứng --- tổng lớn nhất của đoạn con được yêu cầu.

Example

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

5
2
0

Trong một lễ hội điện ảnh hoành tráng, một danh sách dài gồm \(n\) bộ phim đã được công bố. Bạn, một người yêu điện ảnh cuồng nhiệt, muốn xem càng nhiều bộ phim càng tốt. Tuy nhiên, bạn chỉ có thể xem trọn vẹn một bộ phim và không thể xem hai bộ phim cùng lúc. Bạn phải lên một lịch trình xem phim thông minh để tối đa hóa số lượng phim có thể thưởng thức.

Bạn được cung cấp danh sách \(n\) bộ phim. Đối với mỗi bộ phim, bạn biết chính xác thời gian bắt đầu (\(a_i\)) và thời gian kết thúc (\(b_i\)) của nó. Bạn chỉ có thể xem một bộ phim tại một thời điểm, nghĩa là nếu bạn xem một bộ phim kết thúc vào lúc \(t\), bạn chỉ có thể bắt đầu xem bộ phim tiếp theo vào thời điểm \(t\) hoặc muộn hơn.

Với danh sách các bộ phim đã cho, hãy xác định số lượng bộ phim tối đa bạn có thể xem trọn vẹn.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là tổng số bộ phim.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a < b \le 10^9\)), lần lượt là thời gian bắt đầu và kết thúc của một bộ phim.

Output

In ra một số nguyên duy nhất là số lượng phim tối đa có thể xem.

Example

3
3 5
4 9
5 8

2