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

Thuận là một học sinh yêu thích nghiên cứu về số học. Một chủ đề mà Thuận đang nghiên cứu là những số mà các chữ số của nó đôi một khác nhau, ví dụ như \(0, 1, 2, 10, 102, 123, \dots\)

Để việc nghiên cứu được thuận lợi, Thuận muốn viết một chương trình nhập vào số \(X\) và trả ra kết quả là số \(Y\) mà:

• \(Y\) là một số có các chữ số đôi một khác nhau;
• \(Y > X\);
• \(Y\) nhỏ nhất có thể.

Hãy giúp Thuận viết một chương trình như thế.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu tiên gồm số nguyên \(T\) là số bộ dữ liệu (\(T \leq 50\));
• Tiếp theo là \(T\) dòng, mỗi dòng ghi một số \(X\) cần tính (\(0 \leq X \leq 10^9\)).

Output

• Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với bộ dữ liệu vào.

Example

3
1
10
98

2
12
102

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm có \(X \leq 10^6\).
• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm không có ràng buộc gì thêm.

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.