Android Service: Restarting once killed or removed from task stack from phone(Clear All) tasks

I am trying to run my service continuously in background. I understand it will drain a lot of battery but still it is a use case for me.

Case 1: Starting BackgroundService using startService(intent) method. Case 2: Starting a BoundService using bindService(intent,serviceConnection, Context.BIND_AUTO_CREATE);

In both the case, my service onStartCommand code is like below,

 @Override
public int onStartCommand(Intent intent, int flags, int startId) {
    new Thread(new Runnable() {
        @Override
        public void run() {
            while(count < 10000){
                try {
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                count++;

            }

        }
    }).start();
    // TODO: flag not start itself when stopped
    // TODO: use START_STICKY to keep running
    return START_STICKY;
}

Scenario when my service does not die means it will keep running:

case 1: If I press HOME button. case 2: If I press back and come out of the application.

Scenario when my service will definitely be killed:

case 1: If I remove my application from task stack of the phone. case 2: I go to settings and stop the service.

I want my service to get started once it will be killed in either of the scenarios mentioned above.

I have referred many questions from stackoverflow to do like this,

  @Override
    public void onDestroy() {
        super.onDestroy();

        startService(new Intent(this, BackgroundService.class));
    }

    @Override
    public void onTaskRemoved(Intent rootIntent) {
        super.onTaskRemoved(rootIntent);

        startService(new Intent(this, BackgroundService.class));

    }

But definitely onDestroy() is not that kind of method which will be called every time. I have checked it in my logs.