from itertools import groupby
from timeit import timeit
import random
 
 
def inplace(d):
    m_d = [[x,0] for x in d]
 
    mark = 0
    _ = iter(range(len(m_d)-1))
    for i in _:
        while (m_d[i+1][0]-m_d[i][0] <2) and (i<len(m_d)-2):
            m_d[i][1] = mark
            next(_)
            i+=1
        m_d[i][1] = mark
        mark +=1
    #  проверка на то, что последние элемент входит в маркируемый блок
    if m_d[len(m_d)-1][0] - m_d[len(m_d)-2][0] <2:
        m_d[len(m_d)-1][1] = m_d[len(m_d)-2][1]
    return m_d
 
 
def markgroups(elems):
    def getkey(idx):
        "По номеру элемента возвращает ключ его группы"
        return elems[idx] - idx
 
    groups = (group
              for _, group in groupby(range(len(elems)), key=getkey))
 
    return [[elems[idx], group_idx]
            for group_idx, group in enumerate(groups)
            for idx in group]
 
 
data = [x for x in range(1000000) if random.random() < 0.8]
 
 
print('inplace:    {:.4f} s'.format(
    timeit('inplace(data)',
           setup='from __main__ import inplace, data',
           number=1)))
print('markgroups: {:.4f} s'.format(
    timeit('markgroups(data)',
           setup='from __main__ import markgroups, data',
           number=1)))
 
a = inplace(data)
b = markgroups(data)
 
assert a == b, "Результаты различаются"

ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGdyb3VwYnkKZnJvbSB0aW1laXQgaW1wb3J0IHRpbWVpdAppbXBvcnQgcmFuZG9tCgoKZGVmIGlucGxhY2UoZCk6CiAgICBtX2QgPSBbW3gsMF0gZm9yIHggaW4gZF0KCiAgICBtYXJrID0gMAogICAgXyA9IGl0ZXIocmFuZ2UobGVuKG1fZCktMSkpCiAgICBmb3IgaSBpbiBfOgogICAgICAgIHdoaWxlIChtX2RbaSsxXVswXS1tX2RbaV1bMF0gPDIpIGFuZCAoaTxsZW4obV9kKS0yKToKICAgICAgICAgICAgbV9kW2ldWzFdID0gbWFyawogICAgICAgICAgICBuZXh0KF8pCiAgICAgICAgICAgIGkrPTEKICAgICAgICBtX2RbaV1bMV0gPSBtYXJrCiAgICAgICAgbWFyayArPTEKICAgICMgINC/0YDQvtCy0LXRgNC60LAg0L3QsCDRgtC+LCDRh9GC0L4g0L/QvtGB0LvQtdC00L3QuNC1INGN0LvQtdC80LXQvdGCINCy0YXQvtC00LjRgiDQsiDQvNCw0YDQutC40YDRg9C10LzRi9C5INCx0LvQvtC6CiAgICBpZiBtX2RbbGVuKG1fZCktMV1bMF0gLSBtX2RbbGVuKG1fZCktMl1bMF0gPDI6CiAgICAgICAgbV9kW2xlbihtX2QpLTFdWzFdID0gbV9kW2xlbihtX2QpLTJdWzFdCiAgICByZXR1cm4gbV9kCgoKZGVmIG1hcmtncm91cHMoZWxlbXMpOgogICAgZGVmIGdldGtleShpZHgpOgogICAgICAgICLQn9C+INC90L7QvNC10YDRgyDRjdC70LXQvNC10L3RgtCwINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINC60LvRjtGHINC10LPQviDQs9GA0YPQv9C/0YsiCiAgICAgICAgcmV0dXJuIGVsZW1zW2lkeF0gLSBpZHgKCiAgICBncm91cHMgPSAoZ3JvdXAKICAgICAgICAgICAgICBmb3IgXywgZ3JvdXAgaW4gZ3JvdXBieShyYW5nZShsZW4oZWxlbXMpKSwga2V5PWdldGtleSkpCgogICAgcmV0dXJuIFtbZWxlbXNbaWR4XSwgZ3JvdXBfaWR4XQogICAgICAgICAgICBmb3IgZ3JvdXBfaWR4LCBncm91cCBpbiBlbnVtZXJhdGUoZ3JvdXBzKQogICAgICAgICAgICBmb3IgaWR4IGluIGdyb3VwXQoKCmRhdGEgPSBbeCBmb3IgeCBpbiByYW5nZSgxMDAwMDAwKSBpZiByYW5kb20ucmFuZG9tKCkgPCAwLjhdCgoKcHJpbnQoJ2lucGxhY2U6ICAgIHs6LjRmfSBzJy5mb3JtYXQoCiAgICB0aW1laXQoJ2lucGxhY2UoZGF0YSknLAogICAgICAgICAgIHNldHVwPSdmcm9tIF9fbWFpbl9fIGltcG9ydCBpbnBsYWNlLCBkYXRhJywKICAgICAgICAgICBudW1iZXI9MSkpKQpwcmludCgnbWFya2dyb3VwczogezouNGZ9IHMnLmZvcm1hdCgKICAgIHRpbWVpdCgnbWFya2dyb3VwcyhkYXRhKScsCiAgICAgICAgICAgc2V0dXA9J2Zyb20gX19tYWluX18gaW1wb3J0IG1hcmtncm91cHMsIGRhdGEnLAogICAgICAgICAgIG51bWJlcj0xKSkpCgphID0gaW5wbGFjZShkYXRhKQpiID0gbWFya2dyb3VwcyhkYXRhKQoKYXNzZXJ0IGEgPT0gYiwgItCg0LXQt9GD0LvRjNGC0LDRgtGLINGA0LDQt9C70LjRh9Cw0Y7RgtGB0Y8i