import random
import heapq
heap = []
subseqs = {}
prevElem = []
bestL = 0
def merge(x, p, d):
length1 = subseqs[d][1][p][0]
length2 = subseqs[d][0][x][0]
length = length1 + 1 + length2
begin = subseqs[d][1][p][1]
end = subseqs[d][0][x][1]
del subseqs[d][0][begin]
del subseqs[d][1][end]
del subseqs[d][0][x]
del subseqs[d][1][p]
subseqs[d][0][begin] = (length, end)
subseqs[d][1][end] = (length, begin)
def growLeft(x, p, d):
length = 1 + subseqs[d][0][x][0]
end = subseqs[d][0][x][1]
del subseqs[d][1][end]
del subseqs[d][0][x]
subseqs[d][0][p] = (length, end)
subseqs[d][1][end] = (length, p)
def growRight(x, p, d):
length = subseqs[d][1][p][0] + 1
begin = subseqs[d][1][p][1]
del subseqs[d][0][begin]
del subseqs[d][1][p]
subseqs[d][0][begin] = (length, x)
subseqs[d][1][x] = (length, begin)
def insert(x, p, d):
subseqs[d][0][p] = (1, x)
subseqs[d][1][x] = (1, p)
def update(x, p, d):
if d not in subseqs:
heapq.heappush(heap, d)
subseqs[d] = ({},{})
if x in subseqs[d][0]:
if p in subseqs[d][1]:
merge(x, p, d)
else:
growLeft(x, p, d)
else:
if p in subseqs[d][1]:
growRight(x, p, d)
else:
insert(x, p, d)
def init(src):
prevElem.insert(0, -1)
for i in range(1, len(src)):
prevElem.insert(i, i-1)
d = src[i] - src[i-1]
update(i, i-1, d)
def chooseTheBest(d):
global bestL
l = max(list(zip(*subseqs[d][0].values()))[0])
if l > bestL:
bestL = l
def updateIndexes(src, d):
for end in subseqs[d][1].keys():
l = subseqs[d][1][end][0]
i = end
for n in range(l):
link = prevElem[i]
if link != 0:
prevElem[i] -= 1
d2 = src[i] - src[prevElem[i]]
update(i, prevElem[i], d2)
i = link
def findLESS(src):
global bestL
init(src)
while len(heap) > 0:
#print(subseqs)
d = heapq.heappop(heap)
chooseTheBest(d)
updateIndexes(src, d)
del subseqs[d]
return bestL
a = [random.randint(0,20000) for r in range(20000)]
s = list(set(a))
print(findLESS(s) + 1)
aW1wb3J0IHJhbmRvbQppbXBvcnQgaGVhcHEKCgpoZWFwID0gW10Kc3Vic2VxcyA9IHt9CnByZXZFbGVtID0gW10KYmVzdEwgPSAwCgoKZGVmIG1lcmdlKHgsIHAsIGQpOgogIGxlbmd0aDEgPSBzdWJzZXFzW2RdWzFdW3BdWzBdCiAgbGVuZ3RoMiA9IHN1YnNlcXNbZF1bMF1beF1bMF0KICBsZW5ndGggPSBsZW5ndGgxICsgMSArIGxlbmd0aDIKICBiZWdpbiA9IHN1YnNlcXNbZF1bMV1bcF1bMV0KICBlbmQgPSBzdWJzZXFzW2RdWzBdW3hdWzFdCiAgZGVsIHN1YnNlcXNbZF1bMF1bYmVnaW5dCiAgZGVsIHN1YnNlcXNbZF1bMV1bZW5kXQogIGRlbCBzdWJzZXFzW2RdWzBdW3hdCiAgZGVsIHN1YnNlcXNbZF1bMV1bcF0KICBzdWJzZXFzW2RdWzBdW2JlZ2luXSA9IChsZW5ndGgsIGVuZCkKICBzdWJzZXFzW2RdWzFdW2VuZF0gPSAobGVuZ3RoLCBiZWdpbikKCgpkZWYgZ3Jvd0xlZnQoeCwgcCwgZCk6CiAgbGVuZ3RoID0gMSArIHN1YnNlcXNbZF1bMF1beF1bMF0KICBlbmQgPSBzdWJzZXFzW2RdWzBdW3hdWzFdCiAgZGVsIHN1YnNlcXNbZF1bMV1bZW5kXQogIGRlbCBzdWJzZXFzW2RdWzBdW3hdCiAgc3Vic2Vxc1tkXVswXVtwXSA9IChsZW5ndGgsIGVuZCkKICBzdWJzZXFzW2RdWzFdW2VuZF0gPSAobGVuZ3RoLCBwKQoKCmRlZiBncm93UmlnaHQoeCwgcCwgZCk6CiAgbGVuZ3RoID0gc3Vic2Vxc1tkXVsxXVtwXVswXSArIDEKICBiZWdpbiA9IHN1YnNlcXNbZF1bMV1bcF1bMV0KICBkZWwgc3Vic2Vxc1tkXVswXVtiZWdpbl0KICBkZWwgc3Vic2Vxc1tkXVsxXVtwXQogIHN1YnNlcXNbZF1bMF1bYmVnaW5dID0gKGxlbmd0aCwgeCkKICBzdWJzZXFzW2RdWzFdW3hdID0gKGxlbmd0aCwgYmVnaW4pCgoKZGVmIGluc2VydCh4LCBwLCBkKToKICBzdWJzZXFzW2RdWzBdW3BdID0gKDEsIHgpCiAgc3Vic2Vxc1tkXVsxXVt4XSA9ICgxLCBwKQoKCmRlZiB1cGRhdGUoeCwgcCwgZCk6CiAgaWYgZCBub3QgaW4gc3Vic2VxczoKICAgIGhlYXBxLmhlYXBwdXNoKGhlYXAsIGQpCiAgICBzdWJzZXFzW2RdID0gKHt9LHt9KQoKICBpZiB4IGluIHN1YnNlcXNbZF1bMF06CiAgICBpZiBwIGluIHN1YnNlcXNbZF1bMV06CiAgICAgIG1lcmdlKHgsIHAsIGQpCiAgICBlbHNlOgogICAgICBncm93TGVmdCh4LCBwLCBkKQogIGVsc2U6CiAgICBpZiBwIGluIHN1YnNlcXNbZF1bMV06CiAgICAgIGdyb3dSaWdodCh4LCBwLCBkKQogICAgZWxzZToKICAgICAgaW5zZXJ0KHgsIHAsIGQpCgoKZGVmIGluaXQoc3JjKToKICBwcmV2RWxlbS5pbnNlcnQoMCwgLTEpCiAgZm9yIGkgaW4gcmFuZ2UoMSwgbGVuKHNyYykpOgogICAgcHJldkVsZW0uaW5zZXJ0KGksIGktMSkKICAgIGQgPSBzcmNbaV0gLSBzcmNbaS0xXQoKICAgIHVwZGF0ZShpLCBpLTEsIGQpCgoKZGVmIGNob29zZVRoZUJlc3QoZCk6CiAgZ2xvYmFsIGJlc3RMCiAgbCA9IG1heChsaXN0KHppcCgqc3Vic2Vxc1tkXVswXS52YWx1ZXMoKSkpWzBdKQogIGlmIGwgPiBiZXN0TDoKICAgIGJlc3RMID0gbAoKCmRlZiB1cGRhdGVJbmRleGVzKHNyYywgZCk6CiAgZm9yIGVuZCBpbiBzdWJzZXFzW2RdWzFdLmtleXMoKToKICAgIGwgPSBzdWJzZXFzW2RdWzFdW2VuZF1bMF0KICAgIGkgPSBlbmQKCiAgICBmb3IgbiBpbiByYW5nZShsKToKICAgICAgbGluayA9IHByZXZFbGVtW2ldCgogICAgICBpZiBsaW5rICE9IDA6CiAgICAgICAgcHJldkVsZW1baV0gLT0gMQogICAgICAgIGQyID0gc3JjW2ldIC0gc3JjW3ByZXZFbGVtW2ldXQogICAgICAgIHVwZGF0ZShpLCBwcmV2RWxlbVtpXSwgZDIpCiAgICAgICAgaSA9IGxpbmsKCgpkZWYgZmluZExFU1Moc3JjKToKICBnbG9iYWwgYmVzdEwKICBpbml0KHNyYykKCiAgd2hpbGUgbGVuKGhlYXApID4gMDoKICAgICNwcmludChzdWJzZXFzKQogICAgZCA9IGhlYXBxLmhlYXBwb3AoaGVhcCkKICAgIGNob29zZVRoZUJlc3QoZCkKICAgIHVwZGF0ZUluZGV4ZXMoc3JjLCBkKQogICAgZGVsIHN1YnNlcXNbZF0KCiAgcmV0dXJuIGJlc3RMCgoKYSA9IFtyYW5kb20ucmFuZGludCgwLDIwMDAwKSBmb3IgciBpbiByYW5nZSgyMDAwMCldIApzID0gbGlzdChzZXQoYSkpCgpwcmludChmaW5kTEVTUyhzKSArIDEpCg==