Conveyor
To transport materials from workshop A to workshop B, a conveyor belt is used. Materials are packed in identical containers and placed on the belt sequentially as they are produced in workshop A. Each container has an urgency level for processing in workshop B. To sort the containers by urgency, a buffer is employed at the end of the conveyor, just before entering workshop B. The buffer operates in steps, allowing the following actions at each step:
Move the first container from the belt directly to workshop B;
Move the first container from the belt to storage (in storage, each new container is placed on top of the previous one);
Move the top container from storage to workshop B.
Write a program called PIPELINE that, given a sequence of containers, determines whether it is possible to sort them by urgency using the described buffer system.
Input
The input file begins with the number of tests N on the first line. Each of the following N lines describes a separate test, containing an integer K (1 ≤ K ≤ 10000) — the number of containers in the sequence, followed by K real numbers representing the urgency levels of the containers in the order they arrive from workshop A (lower numbers indicate higher urgency).
Output
Each line of the output file should provide the result for one test. Output 1 if sorting by urgency is possible, or 0 if it is not.