You are given an array a[1 . . n] of the n politicians on your lobbying list. each politician a[i] has a type t(a[i]) ∈ {soc, tea, oth}. you are asked to rearrange the array a so that all of the socialists come first, then all the others, then all the tea partiers. the only operations permitted on the array are: (i) for a particular i, query t(a[i]); and (ii) for two particular indices i and j, swap a[i] and a[j]. (for example, you cannot copy elements from the array to an auxiliary array.) give an algorithm that runs in time o(n) to perform your assigned task.