이상한 배열

면접 대비

시간 제한1초메모리 제한1024 MB

요약

배열에서 같은 값을 가진 두 위치 사이에 있는 모든 원소가 그 값 이하인지 판별한다.

문제

길이가 $N$ 인 배열 $A$ 가 주어진다. 배열 $A$ 가 아래 조건을 만족한다면 이 배열 $A$ 를 이상한 배열이라 한다.

$A\_i=A\_j$ 를 만족하는 정수 $1 \le i,j \le N$ 와 $i < k < j$ 를 만족하는 정수 $k$ 에 대해, 항상 $A\_k \le A\_i$ 을 만족한다.

배열 $A$ 가 주어질 때 $A$ 가 이상한 배열인지 확인하여라.

첫 번째 줄에 테스트케이스의 수 $T$ 가 주어진다. ( $1\le T\le 200\ 000$ )

각 테스트케이스에 대해, 첫 번째 줄에 배열의 길이 $N$ 이 주어진다. ( $1\leq N\leq 200\\, 000$ )

두 번째 줄에는 배열의 원소를 나타내는 $N$ 개의 정수 $A\_1,A\_2,\ldots,A\_N$ 이 공백으로 구분되어 주어진다. ( $1\leq A\_i\leq N$ )

모든 테스트케이스에 대해 $N$ 의 합이 $200\\, 000$ 이하임이 보장된다.

각 테스트케이스에 대해 주어진 배열이 이상한 배열이면 Yes, 아니라면 No를 출력한다.

예제 1

입력

6
3
1 2 3
5
1 1 2 2 3
6
1 2 3 1 2 3
9
6 3 2 3 6 4 1 4 6
7
4 3 2 3 1 3 4
9
6 3 1 3 6 4 1 4 6

예상 출력

Yes
Yes
No
Yes
Yes
No