The greater metropolitan area of Bovinopolis consists of a line of N pastures (1≤N≤3⋅105), each containing a single cow, which is either a Holstein or a Guernsey.
The government of Bovinopolis wants to divide the greater metropolitan area into some number of contiguous districts, so that each district contains at most K pastures (1≤K≤N), and every pasture is contained in exactly one district. Since the government is currently controlled by Holsteins, they want to find a way to redistrict which minimizes the number of Guernsey-majority or tied districts (a district is tied if the number of Guernseys equals the number of Holsteins).
A concerned coalition of Guernseys is trying to figure out how much damage might be done by the government's redistricting. Help them figure out the worst-case minimum number of districts which are either Guernsey-majority or tied.
7 2 HGHGGHG
3
7 2
HGHGGHG3