/*
TASK: seq
LANG: C++
*/

#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define pb push_back

struct sequence {
    int last, prelast;
};

int main( void ) {
    
    int total, current, temp;
    sequence first, second;
    string answer;
    int numbers[ 100000 ];
    bool isGood = true;
    
    cin >> total;
    
    for( int i = 0; i < total; ++i ) {
         
         
         cin >> current;
         
         // Read the numbers.
         
         for( int j = 0; j < current; ++j ) { 
              cin >> numbers[ j ];
         }
         
         // Put the first number in the first sequnce.
         first.last = numbers[ 0 ];
         first.prelast = 0;
         second.last = 0;
         second.prelast = 0;
         
         isGood = true;
         
         for( int j = 1; j < current; ++j ) {
         
              // Check if it is possible to put in the second.
              if( numbers[ j ] < first.last ) {
                  
                   second.prelast = second.last;
                   second.last = numbers[ j ];
                   
                   if( second.last < second.prelast ) {
                       isGood = false;
                       break;
                   }
                  
              }

              
              else { 
                  first.prelast = first.last;
                  first.last = numbers[ j ];
              }    
         }
         
         if( isGood ) answer.pb( '1' );
         else answer.pb( '0' );
         
    }
    
    cout << answer;
    
    return 0;        
}

