포뮬러 원

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

요약

각 출발 순위의 차가 몇 번 추월했는지 주어질 때, 그러한 추월 횟수를 정확히 만들어 내는 경주가 존재하는지 판정한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학, 구현
정답자: 아직 제출이 없습니다

문제

꼬마 바이티는 매년 바이트타운과 바이트버그를 잇는 트랙에서 열리는 포뮬러 원 경주를 즐겨 봅니다. 그가 가장 좋아하는 순간은 추월이며, 되도록 많은 추월을 보고 싶어 합니다.

바이티는 $n$ 대의 자동차가 참가하는 경주를 상상합니다. 출발 위치가 $i$ 번인 자동차(각 $1 \le i \le n$ )는 경주 동안 정확히 $a_i$ 번 추월을 합니다. 편의상 어느 순간에도 추월은 최대 한 번만 일어나며, 그 추월에는 정확히 두 대의 자동차만 관여한다고(한 대가 다른 한 대를 앞지른다고) 가정합니다.

이러한 경주가 과연 가능한지 바이티가 판단할 수 있도록 도와주세요.

입력

첫 번째 줄에 테스트 케이스의 수 $t$ 가 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫 번째 줄에는 경주에 참가하는 자동차의 수 $n$ ( $1 \le n \le 1\,000\,000$ )이 주어집니다. 두 번째 줄에는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ )이 주어지며, $a_i$ 는 출발 위치가 $i$ 번인 자동차가 한 추월의 횟수입니다.

하나의 입력 파일 전체 크기는 20 MB를 넘지 않습니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 설명된 경주가 가능하면 TAK(폴란드어로 "예")을, 불가능하면 NIE(폴란드어로 "아니오")를 출력합니다.

예제2

예제 1
입력
```
3
2
0 1
3
0 1 4
3
1 1 3
```
예상 출력
```
TAK
NIE
TAK
```
예제 2
입력
```
4
1
0
1
1
2
0 0
2
0 1
```
예상 출력
```
TAK
NIE
TAK
TAK
```