Hoof, Paper, Scissors (Gold)

You have probably heard of the game "Rock, Paper, Scissors." The cows like to play a similar game called "Hoof, Paper, Scissors."

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each other. They both count to three, and then each simultaneously makes a gesture representing either a hoof, a piece of paper, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors beat paper (since scissors can cut paper), and paper beats hoof (since a hoof can get a papercut). For example, if the first cow makes a "hoof" gesture and the second cow makes a "paper" gesture, the second cow wins. Of course, a game can also end in a tie if both cows make the same gesture.

Farmer John wants to play $n$ games of "Hoof, Paper, Scissors" against his prize cow, Bessie. Bessie, being an expert at the game, can predict each of FJ's gestures before he makes it. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same gesture multiple times in a row. In fact, she is only willing to switch gestures at most $k$ times over the entire sequence of games. For example, if k = 2, she might play "hoof" for the first few games, then switch to "paper" for a while, and finally switch back to "hoof" for the remaining games.

Given the sequence of gestures FJ will play, determine the maximum number of games Bessie can win.