만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

멜로디

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

요약
노트 1부터 N까지를 각각 a_i번씩 사용하고, 매번 인접한 번호로 이동하며, 노트 1에서 시작하는 멜로디를 만들 수 있는지 판별합니다.
난이도

보통10점 중 6점

유형
수학, 그래프, 누적 합
정답자
아직 제출이 없습니다

문제

작곡을 좋아하는 성현이는 NN개의 음만을 사용해서 멜로디를 만들려고 합니다. 각 음에는 11번부터 NN번까지 번호가 매겨져 있습니다. NN개의 음을 원하는 순서대로 나열하면 멜로디가 됩니다.

성현이는 다음 규칙에 따라 멜로디를 만들려고 합니다.

  • 멜로디의 첫 번째 음은 11번 음이어야 한다.
  • 멜로디가 자연스러워야 하므로 xx번 음 뒤에는 x−1x-1번 또는 x+1x+1번 음이 와야 한다.
  • 멜로디에는 1,2,⋯ ,N1,2,\cdots ,N번 음이 각각 a1,a2,⋯ ,aNa_1,a_2,\cdots ,a_N개씩 포함되어야 한다.

a1,a2,⋯ ,aNa_1,a_2,\cdots ,a_N이 주어질 때, 위 규칙을 만족하는 멜로디를 만들 수 있는지 구해보자.

입력

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

각 테스트 케이스의 첫째 줄에 정수 N(1≤N≤200 000)N(1\le N\le 200\, 000)이 주어진다.

각 테스트 케이스의 둘째 줄에 정수 a1,a2,⋯ ,aN(1≤ai≤109)a_1,a_2,\cdots ,a_N(1\le a_i\le 10^9)이 공백으로 구분되어 주어진다.

모든 테스트 케이스의 NN의 합은 200 000200\, 000 이하이다.

출력

각 테스트 케이스마다 규칙을 만족하는 멜로디를 만들 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제1

  1. 예제 1

    입력
    8
2
2 1
4
1 2 3 4
1
1
3
1 2 3
5
1 2 2 2 1
10
1 1 1 1 1 1 1 1 1 1
6
2 3 1 2 3 2
6
3 4 2 3 4 2
    예상 출력
    YES
NO
YES
NO
YES
YES
NO
YES