21
Pyth, 40 36 31 30 bytes
Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ
Try it online: Demonstration or Test Suite
Each of the big test-cases finishes in a couple of seconds.
Explanation:
First I'll explain the method and why it works. I'll do this with the example list: [7, 2, 13, 9].
The first two numb...