---

def getitem(self, idx):
    """lst[idx]"""
    return self._get_node(idx).val

def _get_node(self, idx):
    if idx < 0:
        idx += self.size
    if idx < 0 or idx >= self.size:
        raise IndexError("out of range")
    if idx < self.size // 2:
        cur = self.head
        for _ in range(idx):
            cur = cur.next
    else:
        cur = self.tail
        for _ in range(self.size - 1 - idx):
            cur = cur.prev
    return cur