Dãy "Lên bờ xuống ruộng"
Xem PDF
Điểm:
250
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy \(a\) gồm \(n\) phần tử \(a_1,a_2,...,a_n\).
Dãy \(a\) được gọi là dãy "Lên bờ xuống ruộng" nếu tồn tại phần tử \(i(1\le i\le n)\) thoả mãn : \(a_1<a_2<...<a_{i-1}<a_i>a_{i+1}>...>a_{n-1}>a_n\).
Yêu cầu: Cho một dãy \(b\) gồm \(m\) phần tử \(b_1,b_2,...,b_m\) bất kì. Nhiệm vụ của bạn là từ mảng \(b\) chọn ra các phần tử để tạo thành dãy \(a\) sao cho \(a\) là dãy "Lên bờ xuống ruộng" và số lượng phần tử của dãy \(a\) là nhiều nhất có thể. Nếu có nhiều đáp án, in ra bất kì.
Input
- Dòng thứ nhất chứa số nguyên \(m\)
- Dòng thứ hai chứa \(m\) số nguyên \(b_1,b_2,...,b_m\)
Output
- Dòng thứ nhất chứa số lượng phần tử của dãy \(a\)
- Dòng thứ hai thể hiện các phần tử của dãy \(a\)
Constraints
- \(1\leq m\leq 10^5\)
- \(1\leq b_i\leq 5000\)
Example
Test 1
Input
3
1 2 3 Output
3
1 2 3
Bình luận
có phải chọn liên tiếp phải ko mn
Ủa sao đề nói a1<a2<...<ai−1\<ai>ai+1>...>an−1>an mà sao test vd ra 1 2 3 ai giải thích đề giùm em với