#!/usr/bin/env python
from itertools import groupby
def longest_subarray(input_list):
assert all(v > 0 for v in input_list)
# sort (index, value) pairs by value O(n*log(n))
# radix_sort(), count_sort() won't be O(n) if there is no limit on integers
value = lambda (i, v): v
L = sorted(enumerate(input_list), key=value)
no_duplicates = all(len(list(same_value_group)) == 1
for _, same_value_group in groupby(L, key=value)) # O(n)
start, end = 0, 0 # longest subarray indices
if no_duplicates:
# O(n/m) * O(m) = O(n) time; O(m) space
# group consecutive runs (current = prev + 1)
for _, g in groupby(enumerate(L), key=lambda (j, (i, v)): j - v):
indices = [i for _, (i, v) in g] # O(m)
assert all(input_list[currenti] == input_list[previ] + 1
for currenti, previ in zip(indices[1:], indices))
maxi, mini = indices[0], indices[0]
for m, i in enumerate(indices):
maxi, mini = max(i, maxi), min(i, mini)
if maxi - mini == m and m >= (end - start):
# found longer "continuous sequence"
start, end = mini, maxi + 1
else:
assert 0, "input with duplicates is not supported"
subarray = input_list[start:end]
assert sorted(subarray) == range(min(subarray), max(subarray) + 1)
return subarray
if __name__ == "__main__":
L = map(int, raw_input().split())
print "Input:", L,
subarray = longest_subarray(L)
print "Output:", subarray
assert len(subarray) == 5
IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCmZyb20gaXRlcnRvb2xzIGltcG9ydCBncm91cGJ5CgpkZWYgbG9uZ2VzdF9zdWJhcnJheShpbnB1dF9saXN0KToKICAgIGFzc2VydCBhbGwodiA+IDAgZm9yIHYgaW4gaW5wdXRfbGlzdCkKICAgICMgc29ydCAoaW5kZXgsIHZhbHVlKSBwYWlycyBieSB2YWx1ZSBPKG4qbG9nKG4pKQogICAgIyByYWRpeF9zb3J0KCksIGNvdW50X3NvcnQoKSB3b24ndCBiZSBPKG4pIGlmIHRoZXJlIGlzIG5vIGxpbWl0IG9uIGludGVnZXJzCiAgICB2YWx1ZSA9IGxhbWJkYSAoaSwgdik6IHYKICAgIEwgPSBzb3J0ZWQoZW51bWVyYXRlKGlucHV0X2xpc3QpLCBrZXk9dmFsdWUpCgogICAgbm9fZHVwbGljYXRlcyA9IGFsbChsZW4obGlzdChzYW1lX3ZhbHVlX2dyb3VwKSkgPT0gMQogICAgICAgICAgICAgICAgICAgICAgICBmb3IgXywgc2FtZV92YWx1ZV9ncm91cCBpbiBncm91cGJ5KEwsIGtleT12YWx1ZSkpICMgTyhuKQogICAgc3RhcnQsIGVuZCA9IDAsIDAgIyBsb25nZXN0IHN1YmFycmF5IGluZGljZXMKICAgIGlmIG5vX2R1cGxpY2F0ZXM6CiAgICAgICAgIyBPKG4vbSkgKiBPKG0pID0gTyhuKSB0aW1lOyBPKG0pIHNwYWNlCiAgICAgICAgIyBncm91cCBjb25zZWN1dGl2ZSBydW5zIChjdXJyZW50ID0gcHJldiArIDEpCiAgICAgICAgZm9yIF8sIGcgaW4gZ3JvdXBieShlbnVtZXJhdGUoTCksIGtleT1sYW1iZGEgKGosIChpLCB2KSk6IGogLSB2KToKICAgICAgICAgICAgaW5kaWNlcyA9IFtpIGZvciBfLCAoaSwgdikgaW4gZ10gIyBPKG0pCiAgICAgICAgICAgIGFzc2VydCBhbGwoaW5wdXRfbGlzdFtjdXJyZW50aV0gPT0gaW5wdXRfbGlzdFtwcmV2aV0gKyAxCiAgICAgICAgICAgICAgICAgICAgICAgZm9yIGN1cnJlbnRpLCBwcmV2aSBpbiB6aXAoaW5kaWNlc1sxOl0sIGluZGljZXMpKQogICAgICAgICAgICBtYXhpLCBtaW5pID0gaW5kaWNlc1swXSwgaW5kaWNlc1swXQogICAgICAgICAgICBmb3IgbSwgaSBpbiBlbnVtZXJhdGUoaW5kaWNlcyk6CiAgICAgICAgICAgICAgICBtYXhpLCBtaW5pID0gbWF4KGksIG1heGkpLCBtaW4oaSwgbWluaSkKICAgICAgICAgICAgICAgIGlmIG1heGkgLSBtaW5pID09IG0gYW5kIG0gPj0gKGVuZCAtIHN0YXJ0KToKICAgICAgICAgICAgICAgICAgICAjIGZvdW5kIGxvbmdlciAiY29udGludW91cyBzZXF1ZW5jZSIKICAgICAgICAgICAgICAgICAgICBzdGFydCwgZW5kID0gbWluaSwgbWF4aSArIDEKICAgIGVsc2U6CiAgICAgICAgYXNzZXJ0IDAsICJpbnB1dCB3aXRoIGR1cGxpY2F0ZXMgaXMgbm90IHN1cHBvcnRlZCIKICAgIHN1YmFycmF5ID0gaW5wdXRfbGlzdFtzdGFydDplbmRdCiAgICBhc3NlcnQgc29ydGVkKHN1YmFycmF5KSA9PSByYW5nZShtaW4oc3ViYXJyYXkpLCBtYXgoc3ViYXJyYXkpICsgMSkKICAgIHJldHVybiBzdWJhcnJheQoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIEwgPSBtYXAoaW50LCByYXdfaW5wdXQoKS5zcGxpdCgpKQogICAgcHJpbnQgIklucHV0OiIsIEwsCiAgICBzdWJhcnJheSA9IGxvbmdlc3Rfc3ViYXJyYXkoTCkKICAgIHByaW50ICJPdXRwdXQ6Iiwgc3ViYXJyYXkKICAgIGFzc2VydCBsZW4oc3ViYXJyYXkpID09IDUK