Given is a list of \(n\) natural numbers. A majority element is an element that occurs more than \(n/2\) times in the list. Design and implement a divide-and-conquer algorithm that determines whether a given list contains a majority element, without sorting the list or using dictionaries.)

Assignment

Write a function majority which takes a list as parameter and which returns the value of the majority element, if the list contains a majority element; otherwise the function returns the value \(-1\).

Examples

>>> majority([1,2,1,3,1,4,1,5,1,6,1,2,1,3,1,4,1,5,1,6,1])
1
>>> majority([1,2,3,4,1,2,3,4])
-1