#include <iostream>
#include <vector>
#include <algorithm>
 
void print_vec(const char* label, const std::vector<int>& vec) {
	std::cout << label << ": ";
	for (int v : vec) {
		std::cout << v << ", ";
	}
	std::cout << "\n";
}
 
int main() {
	std::vector <int> vec1 { 4, 1, 2, 2, 5 };
	std::vector <int> vec2;
 
	print_vec("v1", vec1);
 
	vec2.reserve(vec1.size());
 
    for (int v : vec1) {
    	auto it = std::lower_bound(vec2.begin(), vec2.end(), v);
    	if (it == vec2.end() || *it != v)
    		vec2.emplace(it, v);
    	print_vec("v2", vec2);
    }
 
    print_vec("Fin", vec2);
 
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdm9pZCBwcmludF92ZWMoY29uc3QgY2hhciogbGFiZWwsIGNvbnN0IHN0ZDo6dmVjdG9yPGludD4mIHZlYykgewoJc3RkOjpjb3V0IDw8IGxhYmVsIDw8ICI6ICI7Cglmb3IgKGludCB2IDogdmVjKSB7CgkJc3RkOjpjb3V0IDw8IHYgPDwgIiwgIjsKCX0KCXN0ZDo6Y291dCA8PCAiXG4iOwp9CgppbnQgbWFpbigpIHsKCXN0ZDo6dmVjdG9yIDxpbnQ+IHZlYzEgeyA0LCAxLCAyLCAyLCA1IH07CglzdGQ6OnZlY3RvciA8aW50PiB2ZWMyOwoJCglwcmludF92ZWMoInYxIiwgdmVjMSk7CgkKCXZlYzIucmVzZXJ2ZSh2ZWMxLnNpemUoKSk7CgogICAgZm9yIChpbnQgdiA6IHZlYzEpIHsKICAgIAlhdXRvIGl0ID0gc3RkOjpsb3dlcl9ib3VuZCh2ZWMyLmJlZ2luKCksIHZlYzIuZW5kKCksIHYpOwogICAgCWlmIChpdCA9PSB2ZWMyLmVuZCgpIHx8ICppdCAhPSB2KQogICAgCQl2ZWMyLmVtcGxhY2UoaXQsIHYpOwogICAgCXByaW50X3ZlYygidjIiLCB2ZWMyKTsKICAgIH0KCiAgICBwcmludF92ZWMoIkZpbiIsIHZlYzIpOwogICAgCiAgICAKCXJldHVybiAwOwp9