from bisect import bisect
 
class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0
        self.snaps = {}
        self.values = {}
 
    def set(self, index, value):
        if not (snaps := self.snaps.setdefault(index, [])) or snaps[-1] != self.snap_id:
            snaps.append(self.snap_id)
        self.values.setdefault(index, {})[self.snap_id] = value
 
    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1
 
    def get(self, index, snap_id):
        if snaps := self.snaps.get(index):
            return self.values[index][bisect(snaps, snap_id) - 1]
        return 0
 
a = SnapshotArray(3)
a.set(0, 5)
print(a.snap())
a.set(0, 6)
print(a.get(0, 0))

ZnJvbSBiaXNlY3QgaW1wb3J0IGJpc2VjdAoKY2xhc3MgU25hcHNob3RBcnJheToKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBsZW5ndGgpOgogICAgICAgIHNlbGYuc25hcF9pZCA9IDAKICAgICAgICBzZWxmLnNuYXBzID0ge30KICAgICAgICBzZWxmLnZhbHVlcyA9IHt9CgogICAgZGVmIHNldChzZWxmLCBpbmRleCwgdmFsdWUpOgogICAgICAgIGlmIG5vdCAoc25hcHMgOj0gc2VsZi5zbmFwcy5zZXRkZWZhdWx0KGluZGV4LCBbXSkpIG9yIHNuYXBzWy0xXSAhPSBzZWxmLnNuYXBfaWQ6CiAgICAgICAgICAgIHNuYXBzLmFwcGVuZChzZWxmLnNuYXBfaWQpCiAgICAgICAgc2VsZi52YWx1ZXMuc2V0ZGVmYXVsdChpbmRleCwge30pW3NlbGYuc25hcF9pZF0gPSB2YWx1ZQoKICAgIGRlZiBzbmFwKHNlbGYpOgogICAgICAgIHNlbGYuc25hcF9pZCArPSAxCiAgICAgICAgcmV0dXJuIHNlbGYuc25hcF9pZCAtIDEKCiAgICBkZWYgZ2V0KHNlbGYsIGluZGV4LCBzbmFwX2lkKToKICAgICAgICBpZiBzbmFwcyA6PSBzZWxmLnNuYXBzLmdldChpbmRleCk6CiAgICAgICAgICAgIHJldHVybiBzZWxmLnZhbHVlc1tpbmRleF1bYmlzZWN0KHNuYXBzLCBzbmFwX2lkKSAtIDFdCiAgICAgICAgcmV0dXJuIDAKCmEgPSBTbmFwc2hvdEFycmF5KDMpCmEuc2V0KDAsIDUpCnByaW50KGEuc25hcCgpKQphLnNldCgwLCA2KQpwcmludChhLmdldCgwLCAwKSk=