# Problem 1
class Solution(object):
    def findLucky(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        r = -1
        for i in range(len(arr)):
            if arr.count(i+1) == i+1:
                r = i+1
        return r

# Problem 2
class Solution(object):
    def numTeams(self, rating):
        """
        :type rating: List[int]
        :rtype: int
        """
        n = len(rating)
        numTeams = 0
        # Find the number of teams in increasing order
        for i in range(n):
            for j in range(i,n):
                if rating[j] <= rating[i]:
                    continue
                for k in range(j,n):
                    if rating[k] <= rating[j]:
                        continue
                    numTeams += 1
        for i in range(n):
            for j in range(i,n):
                if rating[j] >= rating[i]:
                    continue
                for k in range(j,n):
                    if rating[k] >= rating[j]:
                        continue
                    numTeams += 1
        return numTeams


# Problem 3
class UndergroundSystem(object):

    def __init__(self):
        self.ids = {}       # A dict of each ID along with start/stop stations and their respective times.
        self.pairs = {}  # A dict of station names where data entries are lists of tuples of start/end times.

    def checkIn(self, id, stationName, t):
        """
        :type id: int
        :type stationName: str
        :type t: int
        :rtype: None
        """
        self.ids[id] = [stationName, t, 0]


    def checkOut(self, id, stationName, t):
        """
        :type id: int
        :type stationName: str
        :type t: int
        :rtype: None
        """
        self.ids[id][2] = t     # Update to the starting time
        pair = (self.ids[id][0], stationName)
        if pair not in self.pairs:
            self.pairs[pair] = []
        self.pairs[pair].append(t - self.ids[id][1])

    def getAverageTime(self, startStation, endStation):
        """
        :type startStation: str
        :type endStation: str
        :rtype: float
        """
        pair = (startStation, endStation)
        pairs = self.pairs
        return sum(pairs[pair])/float(len(pairs[pair]))