In this task, you are supposed to writ an efficient algorithm to check whether the elements of a given list of even length can be rearranged to form a palindrome (not whether the list is already a palindrome).

Recall that a palindrome is a sequence that is the same when read forward or backward, i.e.,seqis a palindrome ifseq==seq[::-1], like for example the string'abba'or the list[1, 2, 2, 1].

In more detail, writing a functioncan_construct_pal(lst)that accepts as input a list of characterslstof even length and that returnsTrueif and only if the elements oflstcan be rearranged to form a palindrome.

For example:

>>> can_construct_pal(['b','c','b','c','a','a']) True >>> can_construct_pal(['1', '8','x','1' ,'d','8']) False 

In addition to being correct, the worst-case complexity of your function should not be worse than O(n log n).

Before writing your function, give at least one paragraph with its explanation, why it is correct, and its computational complexity. You can show this paragraph before or after the function or also as a docstring.

Hint: What property does the number of occurrences of each element in the list have to satisfy for the whole list to be rearrangeable to a palindrome?