Tin học trẻ C1 - Vòng Khu vực miền Bắc 2022

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\), ta sắp xếp lại dãy thành dãy không tăng bằng các bước như sau:

• Tìm số \(i\) nhỏ nhất thỏa mãn tồn tại số \(j\) sao cho \(i < j\) và \(a_i < a_j\).
• Nếu tồn tại số \(i\) như vậy, chuyển số \(a_i\) về cuối dãy.
• Nếu không tồn tại số \(i\) như vậy, kết thúc chương trình.

Yêu cầu

Cho dãy số nguyên ban đầu, hãy tính số bước cần thực hiện.

Input

• Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 3 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).

Output

• Ghi ra thiết bị ra chuẩn một số duy nhất là số bước cần thực hiện.

Example

6
2 4 3 1 2 3

4

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm có \(n \le 500\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(n \le 5000\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(a_i \le 3\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(a_1 \le a_2 \le \dots \le a_n\).
• Có \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho một đa giác lồi có \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Người ta chia đa giác này thành \(m + 1\) đa giác con bằng \(m\) đường chéo (\(m \le n - 3\)). Các đường chéo này cùng với \(n\) cạnh của đa giác đôi một không trùng nhau hay cắt nhau (chỉ có điểm chung tại các đầu mút). Một đa giác con gồm các đỉnh lần lượt \(x_1, x_2, \dots, x_t\) được coi là có giá trị \(\sum_{i=1}^{t} 2^{x_i}\).

Cho đa giác, \(m\) đường chéo và số nguyên dương \(k\) (\(k \le m + 1\)), sắp xếp các đa giác con theo giá trị tăng dần, hãy xác định đa giác con thứ \(k\).

Input

• Dòng đầu gồm ba số nguyên \(n, m, k\) (\(3 \le n \le 5 \cdot 10^5; 0 \le m \le n - 3; 1 \le k \le m + 1\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện một đường chéo trong đa giác.

Output

• Ghi ra thiết bị ra chuẩn các đỉnh của đa giác con thứ \(k\) (các đỉnh được ghi theo thứ tự tăng dần).

Example

6 3 2
1 3
1 4
1 5

1 3 4

Scoring

• Có \(25\%\) số test ứng với \(25\%\) số điểm có \(n \le 50\) và \(m \le 20\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm có \(m = 1\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm có \(m = n - 3\).
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc gì thêm.

Có \(n\) hộp quà có dạng hình khối và cùng chiều cao bằng \(1\), hộp quà thứ \(i\) (\(1 \le i \le n\)) có đáy là \(a_i \times b_i\). Người ta muốn xếp \(n\) hộp quà vào một hộp cũng có chiều cao bằng \(1\) và có diện tích đáy càng nhỏ càng tốt. Các cạnh đáy của các hộp quà phải đặt song song hoặc vuông góc với các cạnh đáy của hộp đựng quà.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ \(i\) (\(1 \le i \le n\)) chứa hai số nguyên dương \(a_i,b_i\) (\(a_i,b_i \le 10^6\)).

Dữ liệu đảm bảo tồn tại một hình hộp chữ nhật có diện tích đáy bằng tổng diện tích dáy của các hộp quà và chứa được hết tất cả các hộp quà.

Output

• Dòng đầu tiên gồm hai số nguyên dương \(W,H\) là kích thước đáy hình hộp để chứa \(n\) hộp quà. Quy ước đặt hộp quà trên hệ trục tọa độ với góc trái dưới là \((0,0)\) và tọa độ phải trên là \((W,H)\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) (\(1 \le i \le n\)) gồm bốn số là tọa độ phải dưới và phải trên mô tả vị trí đặt hộp quà thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 50\).
• Cách tính điểm: Có \(20\) test, mỗi test \(5.0\) điểm. Gọi diện tích dáy của hình hộp cần dùng do thí sinh tìm được là \(c\), \(q\) là tổng diện tích đáy của các hộp quà, khi đó số điểm bạn đạt được cho mỗi test là \(5.0 \times min\{1,\frac{q^2}{c^2}\}\).

Example

3
1 3
2 2
1 2

3 3
0 2 3 3
1 0 3 2
0 0 1 2