class SnapshotArray:

    def __init__(self, length: int):
        self.history_record = defaultdict(list)
        self.count = 0

    def set(self, index: int, val: int) -> None:
        self.history_record[index].append([self.count, val])

    def snap(self) -> int:
        self.count += 1
        return self.count - 1

    def get(self, index: int, snap_id: int) -> int:
        history = self.history_record[index]
        low = 0; high = len(history) - 1
        result = 0
        while (low <= high):
            mid = (low + high)//2

            if history[mid][0] <= snap_id:
                result = history[mid][1]
                low = mid + 1
            else:
                high = mid - 1

        return result

# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)