C++ :: Delete Smallest Part Of List Of Integers To Sort In Non Decreasing Order

I am supposed to make a program that take a list of integers from the user and to delete the smallest part of it in order to make it sorted in non decreasing order ..

example : input : 1 2 3 4 5 8 7 6 7 8 9
output : 1 2 3 4 5 6 7 8 9 ( delete : 8 7 )

I need a code that use a technique similar to the merge function to achieve linear time ..

this code works but it is in quadratic time :

int main () {
cout<<"Enter a list of numnbers ending with the sentinel -999:"<<endl;
int A[1000];
int n = 0;
int x;
cin>>x;
while(x!=-999)

[Code] ....