import random
import heapq
heap = []
subseqs = {}
prevElem = []
bestL = 0
def merge(x, p, rec):
length1 = rec[1][p][0]
length2 = rec[0][x][0]
length = length1 + 1 + length2
begin = rec[1][p][1]
end = rec[0][x][1]
del rec[0][x]
del rec[1][p]
rec[0][begin] = (length, end)
rec[1][end] = (length, begin)
def growLeft(x, p, rec):
length = 1 + rec[0][x][0]
end = rec[0][x][1]
del rec[0][x]
rec[0][p] = (length, end)
rec[1][end] = (length, p)
def growRight(x, p, rec):
length = rec[1][p][0] + 1
begin = rec[1][p][1]
del rec[1][p]
rec[0][begin] = (length, x)
rec[1][x] = (length, begin)
def insert(x, p, rec):
rec[0][p] = (1, x)
rec[1][x] = (1, p)
def update(x, p, d):
if d not in subseqs:
heapq.heappush(heap, d)
subseqs[d] = ({},{})
rec = subseqs[d]
if x in rec[0]:
if p in rec[1]:
merge(x, p, rec)
else:
growLeft(x, p, rec)
else:
if p in rec[1]:
growRight(x, p, rec)
else:
insert(x, p, rec)
def init(src):
prevElem.insert(0, None)
for i in xrange(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])
bestL = max(bestL, l)
def updateIndexes(src, rec):
for end in rec[1].keys():
l = rec[1][end][0]
i = end
for n in xrange(l):
link = prevElem[i]
if link != 0:
prevElem[i] -= 1
d = src[i] - src[prevElem[i]]
update(i, prevElem[i], d)
i = link
def findLESS(src):
global bestL
init(src)
while len(heap) > 0:
d = heapq.heappop(heap)
chooseTheBest(d)
updateIndexes(src, subseqs[d])
del subseqs[d]
if bestL * d > s[-1] - s[0]:
break
return bestL
a = [random.randint(0,40000) for r in xrange(28000)]
s = sorted(list(set(a)))
print(findLESS(s) + 1)
aW1wb3J0IHJhbmRvbQppbXBvcnQgaGVhcHEKCmhlYXAgPSBbXQpzdWJzZXFzID0ge30KcHJldkVsZW0gPSBbXQpiZXN0TCA9IDAKCgpkZWYgbWVyZ2UoeCwgcCwgcmVjKToKICBsZW5ndGgxID0gcmVjWzFdW3BdWzBdCiAgbGVuZ3RoMiA9IHJlY1swXVt4XVswXQogIGxlbmd0aCA9IGxlbmd0aDEgKyAxICsgbGVuZ3RoMgogIGJlZ2luID0gcmVjWzFdW3BdWzFdCiAgZW5kID0gcmVjWzBdW3hdWzFdCiAgZGVsIHJlY1swXVt4XQogIGRlbCByZWNbMV1bcF0KICByZWNbMF1bYmVnaW5dID0gKGxlbmd0aCwgZW5kKQogIHJlY1sxXVtlbmRdID0gKGxlbmd0aCwgYmVnaW4pCgoKZGVmIGdyb3dMZWZ0KHgsIHAsIHJlYyk6CiAgbGVuZ3RoID0gMSArIHJlY1swXVt4XVswXQogIGVuZCA9IHJlY1swXVt4XVsxXQogIGRlbCByZWNbMF1beF0KICByZWNbMF1bcF0gPSAobGVuZ3RoLCBlbmQpCiAgcmVjWzFdW2VuZF0gPSAobGVuZ3RoLCBwKQoKCmRlZiBncm93UmlnaHQoeCwgcCwgcmVjKToKICBsZW5ndGggPSByZWNbMV1bcF1bMF0gKyAxCiAgYmVnaW4gPSByZWNbMV1bcF1bMV0KICBkZWwgcmVjWzFdW3BdCiAgcmVjWzBdW2JlZ2luXSA9IChsZW5ndGgsIHgpCiAgcmVjWzFdW3hdID0gKGxlbmd0aCwgYmVnaW4pCgoKZGVmIGluc2VydCh4LCBwLCByZWMpOgogIHJlY1swXVtwXSA9ICgxLCB4KQogIHJlY1sxXVt4XSA9ICgxLCBwKQoKCmRlZiB1cGRhdGUoeCwgcCwgZCk6CiAgaWYgZCBub3QgaW4gc3Vic2VxczoKICAgIGhlYXBxLmhlYXBwdXNoKGhlYXAsIGQpCiAgICBzdWJzZXFzW2RdID0gKHt9LHt9KQoKICByZWMgPSBzdWJzZXFzW2RdCgogIGlmIHggaW4gcmVjWzBdOgogICAgaWYgcCBpbiByZWNbMV06CiAgICAgIG1lcmdlKHgsIHAsIHJlYykKICAgIGVsc2U6CiAgICAgIGdyb3dMZWZ0KHgsIHAsIHJlYykKICBlbHNlOgogICAgaWYgcCBpbiByZWNbMV06CiAgICAgIGdyb3dSaWdodCh4LCBwLCByZWMpCiAgICBlbHNlOgogICAgICBpbnNlcnQoeCwgcCwgcmVjKQoKCmRlZiBpbml0KHNyYyk6CiAgcHJldkVsZW0uaW5zZXJ0KDAsIE5vbmUpCgogIGZvciBpIGluIHhyYW5nZSgxLCBsZW4oc3JjKSk6CiAgICBwcmV2RWxlbS5pbnNlcnQoaSwgaS0xKQogICAgZCA9IHNyY1tpXSAtIHNyY1tpLTFdCiAgICB1cGRhdGUoaSwgaS0xLCBkKQoKCmRlZiBjaG9vc2VUaGVCZXN0KGQpOgogIGdsb2JhbCBiZXN0TAogIGwgPSBtYXgobGlzdCh6aXAoKnN1YnNlcXNbZF1bMF0udmFsdWVzKCkpKVswXSkKICBiZXN0TCA9IG1heChiZXN0TCwgbCkKCgpkZWYgdXBkYXRlSW5kZXhlcyhzcmMsIHJlYyk6CiAgZm9yIGVuZCBpbiByZWNbMV0ua2V5cygpOgogICAgbCA9IHJlY1sxXVtlbmRdWzBdCiAgICBpID0gZW5kCgogICAgZm9yIG4gaW4geHJhbmdlKGwpOgogICAgICBsaW5rID0gcHJldkVsZW1baV0KCiAgICAgIGlmIGxpbmsgIT0gMDoKICAgICAgICBwcmV2RWxlbVtpXSAtPSAxCiAgICAgICAgZCA9IHNyY1tpXSAtIHNyY1twcmV2RWxlbVtpXV0KICAgICAgICB1cGRhdGUoaSwgcHJldkVsZW1baV0sIGQpCiAgICAgICAgaSA9IGxpbmsKCgpkZWYgZmluZExFU1Moc3JjKToKICBnbG9iYWwgYmVzdEwKICBpbml0KHNyYykKCiAgd2hpbGUgbGVuKGhlYXApID4gMDoKICAgIGQgPSBoZWFwcS5oZWFwcG9wKGhlYXApCiAgICBjaG9vc2VUaGVCZXN0KGQpCiAgICB1cGRhdGVJbmRleGVzKHNyYywgc3Vic2Vxc1tkXSkKICAgIGRlbCBzdWJzZXFzW2RdCgogICAgaWYgYmVzdEwgKiBkID4gc1stMV0gLSBzWzBdOgogICAgICBicmVhawoKICByZXR1cm4gYmVzdEwKCgphID0gW3JhbmRvbS5yYW5kaW50KDAsNDAwMDApIGZvciByIGluIHhyYW5nZSgyODAwMCldCnMgPSBzb3J0ZWQobGlzdChzZXQoYSkpKQoKcHJpbnQoZmluZExFU1MocykgKyAxKQo=