1. 모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다.
2. (C++) endl 쓰지 말고 '\n' 쓰세요. endl은 버퍼를 flush하기 때문에 매우, 매우, 매우 느립니다. 이건 이 문제 뿐만이 아니라 앞으로 푸실 모든 문제에 대해 공통입니다.
3. int a[10000]; 의 원소는 9999까지입니다.
4. 느린 입출력을 써도 시간 초과가 될 수 있습니다. https://www.acmicpc.net/proble... 에서 내가 충분히 빠른 입출력을 쓰고 있는지 확인해 보세요.
5. Pypy를 쓸 경우 print가 아니라 sys.stdout.write를 해야 메모리 초과를 받지 않습니다.

통과는 됐는데 너무 느리다면 다음과 같은 이유가 있습니다.

• 위의 1번의 경우 메모리 보너스가 있는 언어들에는 해당되지 않을 수 있습니다. 하지만 기본적으로 sort는 원소들의 비교를 통해 정렬을 수행하고, O(nlogn)의 시간복잡도를 가집니다. 천만 로그 천만은 2억 3천 정도로 상당히 무겁습니다. 애초에, 이 문제는 그렇게 풀라고 만든 문제가 아닙니다. 이런 식의 풀이를 허용할 거라면 굳이 메모리 제한을 넉넉하게 안 주고 8MB로 빡세게 할 필요가 없죠. 그럼 어떻게 할까요? 힌트는 사실 위에 3번에 있습니다.
• O(nlogn)보다 빠르게 풀 수 있는데도 시간 제한이 3초씩이나 되는 건 바로 입력을 받는 것 자체가 그와 맞먹는 수준의 느린 속도를 자랑하기 때문입니다 (사실 입력량 자체가 O(nlog(최대자릿수))입니다). C++이라면 ios_base::sync_with_stdio(false); 를 하는 것만으로도 엄청난 속도의 향상을 볼 수 있고, Java라면 BufferedReader, Python에서는 sys.stdin.readline이 있습니다 (파이썬은 input()으로는 통과 자체를 못 하는 것으로 알고 있습니다). C 계열의 경우 fread나 mmap을 쓰면 정말 말도 안 되는 속도의 향상을 볼 수 있지만, 이건 해보고 싶은 사람만 해보면 됩니다.