#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
 
int main() {
	list<int> list_1 = {1, 2, 4, 4, 6, 9};
	list<int> list_2 = {1, 0, 4, 4, 7, 8};
	list_1.unique(); // O(n)
	list_2.unique(); // O(n)
 
	size_t counter = 0;
	unordered_map <int, size_t> map;
	size_t i = 0;
 
	for (auto it = list_1.begin(); it != list_1.end(); ++it, ++i) // O(n)
		map.insert( {*it, i} );
 
 
 
	for (int &i : list_2) { // O(n)
		if (map.find(i) != map.end())
			++counter;
	}
 
	cout << "there is " << counter << " identical elements\n";
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWxpc3Q8aW50PiBsaXN0XzEgPSB7MSwgMiwgNCwgNCwgNiwgOX07CglsaXN0PGludD4gbGlzdF8yID0gezEsIDAsIDQsIDQsIDcsIDh9OwoJbGlzdF8xLnVuaXF1ZSgpOyAvLyBPKG4pCglsaXN0XzIudW5pcXVlKCk7IC8vIE8obikKCQoJc2l6ZV90IGNvdW50ZXIgPSAwOwoJdW5vcmRlcmVkX21hcCA8aW50LCBzaXplX3Q+IG1hcDsKCXNpemVfdCBpID0gMDsKCQoJZm9yIChhdXRvIGl0ID0gbGlzdF8xLmJlZ2luKCk7IGl0ICE9IGxpc3RfMS5lbmQoKTsgKytpdCwgKytpKSAvLyBPKG4pCgkJbWFwLmluc2VydCggeyppdCwgaX0gKTsKCQoJCgkJCglmb3IgKGludCAmaSA6IGxpc3RfMikgeyAvLyBPKG4pCgkJaWYgKG1hcC5maW5kKGkpICE9IG1hcC5lbmQoKSkKCQkJKytjb3VudGVyOwoJfQoJCgljb3V0IDw8ICJ0aGVyZSBpcyAiIDw8IGNvdW50ZXIgPDwgIiBpZGVudGljYWwgZWxlbWVudHNcbiI7CgkKCXJldHVybiAwOwp9