new_contents: # Time:  O(n)
  # Space: O(n)
  
  # In the world of Dota2, there are two parties: the Radiant and the Dire.
  #
  # The Dota2 senate consists of senators coming from two parties.
  # Now the senate wants to make a decision about a change in the Dota2 game.
  # The voting for this change is a round-based procedure.
  # In each round, each senator can exercise one of the two rights:
  #
  # Ban one senator's right: 
  # A senator can make another senator lose all his rights in this and all the following rounds.
  # Announce the victory: 
  # If this senator found the senators who still have rights to vote are all from the same party,
  # he can announce the victory and make the decision about the change in the game.
  #
  # Given a string representing each senator's party belonging.
  # The character 'R' and 'D' represent the Radiant party and the Dire party respectively.
  # Then if there are n senators, the size of the given string will be n.
  #
  # The round-based procedure starts from the first senator to the last senator in the given order.
  # This procedure will last until the end of voting. All the senators
  # who have lost their rights will be skipped during the procedure.
  #
  # Suppose every senator is smart enough and will play the best strategy for his own party,
  # you need to predict which party will finally announce the victory and make the change in the Dota2 game.
  # The output should be Radiant or Dire.
  #
  # Example 1:
  # Input: "RD"
  # Output: "Radiant"
  # Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
  # And the second senator can't exercise any rights any more since his right has been banned. 
  # And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
  # Example 2:
  # Input: "RDD"
  # Output: "Dire"
  # Explanation: 
  # The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
  # And the second senator can't exercise any rights anymore since his right has been banned. 
  # And the third senator comes from Dire and he can ban the first senator's right in the round 1. 
  # And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
  # Note:
  # The length of the given string will in the range [1, 10,000].
  
  class Solution(object):
      def predictPartyVictory(self, senate):
          """
          :type senate: str
          :rtype: str
          """
          n = len(senate)
          radiant, dire = collections.deque(), collections.deque()
          for i, c in enumerate(senate):
              if c == 'R':
                  radiant.append(i)
              else:
                  dire.append(i)
          while radiant and dire:
              r_idx, d_idx = radiant.popleft(), dire.popleft()
              if r_idx < d_idx:
                  radiant.append(r_idx+n)
              else:
                  dire.append(d_idx+n)
          return "Radiant" if len(radiant) > len(dire) else "Dire"
  
subject: Create dota2-senate.py