Java Multi-threading

I was solving this question in Java where the user enters a partitioned array. The computer then determines what all elements from that array can be used as pivots. (Pivots are the same pivots that are used in quick-sort i.e before elements before the pivot in the array are all smaller than it and the elements after the pivot are all larger than it).

The main challenge was to solve the problem such that it solves even large arrays in O(nlogn) time. As my logic is quite old-school and obvious, it failed some test-cases in which the program took more than 1 second. I then tried to use the same code but with multi-threading. The created two different threads and then used each one to run the two loops inside the main loop inside the Check() function. Despite this, the program took around a second for the same test-cases and thus, it failed to pass them.

Can someone please explain to me that despite running the two loops independently, why the execution time is not reduced?

Here's the program that I wrote:

import java.util.ArrayList;
import java.util.Scanner;


public class ques1 {

public static int[] arr;

public static void main(String args[])
{
     Scanner in=new Scanner(System.in);
                      //entering the number of elemets
     int n=in.nextInt();
     arr=new int[n];
                      //entering the partitioned array
     for(int i=0;i<n;i++)
          {
        arr[i]=in.nextInt();
          }
                      // array populated
     check();

}
public static void check()
   {    
  ArrayList<Integer> list1=new ArrayList<>();
  ArrayList<Integer> list2=new ArrayList<>();
  int p=0;
  for(int i=0;i<arr.length;i++)
        {  
             for(int k=i+1;k<arr.length;k++)  //a thread for this loop
             {
                  if(!(arr[k]>=arr[i]))
                  {
                  list2.add(0);
                  }
             }

            for(int k=i-1;k>=0;k--)          //a thread for this loop
            {
                 if(!(arr[k]<=arr[i]))
                 {
                 list2.add(0);
                 }

            }
        }

 if(!(list1.contains(0) || list2.contains(0)))
       {
        p++;
       }
    list1.clear();
    list2.clear();


System.out.println(p);
   }



}