Một hoán vị kích thước $n$ là một dãy gồm $n$ số nguyên $a_1,a_2,\ldots,a_n$, trong đó mỗi giá trị từ $1$ đến $n$ xuất hiện đúng một lần.
Dãy $b_1,b_2,\ldots,b_l$ là một dãy con của dãy $a_1,a_2,\ldots,a_n$ nếu có thể thu được $b$ bằng cách xóa một số phần tử khỏi $a$ (nghĩa là $l\le n$ và tồn tại $i_1<i_2<\ldots<i_l$ sao cho $a_{i_t}=b_t$).
- Phần tử $a_i$ của dãy được gọi là một kỷ lục nếu nó lớn hơn hẳn tất cả các phần tử đứng trước (nghĩa là $a_j<a_i$ với mọi $1\le j<i$).
- Phần tử $a_i$ của dãy được gọi là một phản kỷ lục nếu nó nhỏ hơn hẳn tất cả các phần tử đứng trước (nghĩa là $a_j>a_i$ với mọi $1\le j<i$).
Cho một hoán vị $p_1,p_2,\ldots,p_n$ kích thước $n$. Bạn cần chia nó thành hai dãy con không rỗng $q$ và $r$. Nói cách khác, mỗi phần tử của $p$ phải thuộc đúng một trong hai dãy con. Hãy tối đa hóa tổng số kỷ lục trong $q$ và số phản kỷ lục trong $r$.
Dữ liệu vào
Mỗi bài kiểm tra gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $t$ ($1\le t\le 100\,000$), là số bộ dữ liệu. $2t$ dòng tiếp theo mô tả các bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$, là kích thước của hoán vị ($2\le n\le 200\,000$).
Dòng thứ hai của mỗi bộ dữ liệu chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$, là hoán vị ban đầu. Bảo đảm rằng mỗi số từ $1$ đến $n$ xuất hiện đúng một lần trong $p$.
Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $200\,000$.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên: tổng lớn nhất có thể của số kỷ lục trong $q$ và số phản kỷ lục trong $r$ trong cách chia tối ưu.
Nhiệm vụ con
Gọi $N$ là tổng các giá trị $n$ trên tất cả các bộ dữ liệu của một bài kiểm tra.
| Nhiệm vụ con | Điểm | Giới hạn: $n,N$ | Giới hạn bổ sung | Nhiệm vụ con cần thiết | Thông tin chấm bài |
|---|---|---|---|---|---|
| 1 | 21 | $n\le 16$ | $t\le 120$ | Ví dụ | Lỗi đầu tiên |
| 2 | 22 | $n\le 200$, $N\le 2000$ | Ví dụ, 1 | Lỗi đầu tiên | |
| 3 | 14 | $N\le 2\,000$ | Ví dụ, 1–2 | Lỗi đầu tiên | |
| 4 | 10 | $N\le 10\,000$ | Ví dụ, 1–3 | Lỗi đầu tiên | |
| 5 | 13 | $N\le 200\,000$ | Độ dài dãy con giảm dài nhất trong $p$ không vượt quá $2$ | Lỗi đầu tiên | |
| 6 | 20 | $N\le 200\,000$ | Ví dụ, 1–5 | Lỗi đầu tiên |
Ví dụ
Dữ liệu vào 1
4 5 4 1 2 3 5 10 3 8 10 4 1 2 7 9 5 6 3 1 2 3 6 4 2 5 1 6 3
Dữ liệu ra 1
5 6 3 5
Ghi chú
Một cách chia $p$ thành $q$ và $r$ tối ưu trong bộ dữ liệu đầu tiên (các kỷ lục trong $q$ và phản kỷ lục trong $r$ được đóng khung):
- $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
- $r=\boxed{4}$
Một cách chia $p$ thành $q$ và $r$ tối ưu trong bộ dữ liệu thứ hai:
- $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
- $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$