Problem Name: Monsters.

There are N Monsters numbered from 1 to N , each of type Fire, Water or Grass represented by a string A of length N . When two Monsters battle each other, one of them wins according to the following rules: • A Fire Monster always defeats a Grass Monster. • A Water Monster always defeats a Fire Monster. • A Grass Monster always defeats a Water Monster. • In a battle between two Monsters of the same type, either one can win. Answer Q queries of the following form: if the Monsters Lj ...Rj are standing in a line from left to right, and repeatedly, two adjacent Monsters battle each other with the loser leaving the line, how many Monsters can be the last remaining Monster in at least one valid sequence of events?

Problem Link: Monsters