kar[m] = key-index(key, n), valid-idx(kar, ar, m + 1) ⊦ valid-idx(kar[0, key-index(key, n)], ar[n, ar[n].idx:= 0], m)