My full search say that solution exist for n<=22292

There is solution for all n <= 10^5 though I still can not fast enough generate answer

According to my calculations the largest such sequence can be 344001 for the constraints of the problem.

I've solved this problem using DP.
Hint: The maximum sum of numbers for required sequence does not exceed 1568617.

answer for every n exists
there is no possibility to output “impossible”