#include <iostream>
#include <algorithm>
#include <vector>
template <typename T, typename Comp>
void insert_sorted(std::vector<T>& vec, T const& e, Comp const& comp) {
auto const it = std::lower_bound(vec.begin(), vec.end(), e, comp);
if (it != vec.end() and not comp(e, *it)) { return; }
vec.insert(it, e);
}
template <typename T>
void insert_sorted(std::vector<T>& vec, T const& e) {
insert_sorted(vec, e, std::less<T>{});
}
int main() {
int const array[] = { 4, 3, 6, 2, 3, 6, 8, 4 };
std::vector<int> vec;
for (int a: array) {
insert_sorted(vec, a);
}
std::cout << vec.size() << ":";
for (int a: vec) { std::cout << " " << a; }
std::cout << "\n";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnRlbXBsYXRlIDx0eXBlbmFtZSBULCB0eXBlbmFtZSBDb21wPgp2b2lkIGluc2VydF9zb3J0ZWQoc3RkOjp2ZWN0b3I8VD4mIHZlYywgVCBjb25zdCYgZSwgQ29tcCBjb25zdCYgY29tcCkgewoJYXV0byBjb25zdCBpdCA9IHN0ZDo6bG93ZXJfYm91bmQodmVjLmJlZ2luKCksIHZlYy5lbmQoKSwgZSwgY29tcCk7CgkKCWlmIChpdCAhPSB2ZWMuZW5kKCkgYW5kIG5vdCBjb21wKGUsICppdCkpIHsgcmV0dXJuOyB9CgkKCXZlYy5pbnNlcnQoaXQsIGUpOwp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kdm9pZCBpbnNlcnRfc29ydGVkKHN0ZDo6dmVjdG9yPFQ+JiB2ZWMsIFQgY29uc3QmIGUpIHsKCWluc2VydF9zb3J0ZWQodmVjLCBlLCBzdGQ6Omxlc3M8VD57fSk7Cn0KCmludCBtYWluKCkgewoJaW50IGNvbnN0IGFycmF5W10gPSB7IDQsIDMsIDYsIDIsIDMsIDYsIDgsIDQgfTsKCQoJc3RkOjp2ZWN0b3I8aW50PiB2ZWM7Cglmb3IgKGludCBhOiBhcnJheSkgewoJCWluc2VydF9zb3J0ZWQodmVjLCBhKTsKCX0KCQoJc3RkOjpjb3V0IDw8IHZlYy5zaXplKCkgPDwgIjoiOwoJZm9yIChpbnQgYTogdmVjKSB7IHN0ZDo6Y291dCA8PCAiICIgPDwgYTsgfQoJc3RkOjpjb3V0IDw8ICJcbiI7CgkKCXJldHVybiAwOwp9