codeforces#P2000B. Seating in a Bus

Seating in a Bus

Description

In Berland, a bus consists of a row of $n$ seats numbered from $1$ to $n$. Passengers are advised to always board the bus following these rules:

  • If there are no occupied seats in the bus, a passenger can sit in any free seat;
  • Otherwise, a passenger should sit in any free seat that has at least one occupied neighboring seat. In other words, a passenger can sit in a seat with index $i$ ($1 \le i \le n$) only if at least one of the seats with indices $i-1$ or $i+1$ is occupied.

Today, $n$ passengers boarded the bus. The array $a$ chronologically records the seat numbers they occupied. That is, $a_1$ contains the seat number where the first passenger sat, $a_2$ — the seat number where the second passenger sat, and so on.

You know the contents of the array $a$. Determine whether all passengers followed the recommendations.

For example, if $n = 5$, and $a$ = [$5, 4, 2, 1, 3$], then the recommendations were not followed, as the $3$-rd passenger sat in seat number $2$, while the neighboring seats with numbers $1$ and $3$ were free.

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The following describes the input test cases.

The first line of each test case contains exactly one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of seats in the bus and the number of passengers who boarded the bus.

The second line of each test case contains $n$ distinct integers $a_i$ ($1 \le a_i \le n$) — the seats that the passengers occupied in chronological order.

It is guaranteed that the sum of $n$ values across all test cases does not exceed $2 \cdot 10^5$, and that no passenger sits in an already occupied seat.

For each test case, output on a separate line:

  • "YES", if all passengers followed the recommendations;
  • "NO" otherwise.

You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The following describes the input test cases.

The first line of each test case contains exactly one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of seats in the bus and the number of passengers who boarded the bus.

The second line of each test case contains $n$ distinct integers $a_i$ ($1 \le a_i \le n$) — the seats that the passengers occupied in chronological order.

It is guaranteed that the sum of $n$ values across all test cases does not exceed $2 \cdot 10^5$, and that no passenger sits in an already occupied seat.

Output

For each test case, output on a separate line:

  • "YES", if all passengers followed the recommendations;
  • "NO" otherwise.

You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

4
5
5 4 2 1 3
3
2 3 1
4
2 3 1 4
5
1 2 3 5 4
NO
YES
YES
NO

Note

The first test case is explained in the problem statement.