Parry It! (Hard)

**This is the hard version of the problem. In this version, you need to answer for each index $i$ whether a maximal sequence of parries including that index exists.** Chef is playing a videogame, and fighting a particularly difficult boss. After several tries, Chef has learned the attack patterns of the boss and knows exactly what to expect. The boss will perform $N$ attacks, in order. Each at