반산술 순열인가?

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

요약
0부터 n-1까지의 순열이 주어질 때, 값이 등차수열을 이루는 세 위치가 있는지 판별한다.
난이도

보통10점 중 4점

유형
해시맵, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

nn의 순열은 처음 nn개의 자연수 0,1,…,n−10, 1, \dots, n-1 위에서 정의된 전단사(일대일 대응) 함수입니다. 순열 pp가 반산술(antiarithmetic) 이라는 것은, 길이가 22보다 큰 부분수열 중 등차수열을 이루는 것이 하나도 없다는 뜻입니다. 즉, 0≤i<j<k<n0 \le i < j < k < n 이면서 (pi,pj,pk)(p_i, p_j, p_k) 가 등차수열(pj−pi=pk−pjp_j - p_i = p_k - p_j)이 되는 세 인덱스가 존재하지 않아야 합니다.

예를 들어 순열 (2,0,1,4,3)(2, 0, 1, 4, 3) 은 55의 반산술 순열입니다. 반면 (0,5,4,3,1,2)(0, 5, 4, 3, 1, 2) 는 반산술 순열이 아닙니다. 첫 번째·다섯 번째·여섯 번째 항 (0,1,2)(0, 1, 2) 가 등차수열을 이루고, 두 번째·네 번째·다섯 번째 항 (5,3,1)(5, 3, 1) 도 등차수열을 이루기 때문입니다.

주어진 nn의 순열이 반산술 순열인지 판정하세요.

입력

여러 개의 테스트 케이스가 주어지며, 마지막에는 00 하나만 있는 줄이 옵니다. 각 테스트 케이스는 한 줄이며, 자연수 nn (3≤n≤100003 \le n \le 10000) 다음에 콜론(:)이 오고, 그 뒤에 공백으로 구분된 서로 다른 nn개의 수가 나옵니다. 이 nn개의 수는 모두 nn보다 작은 자연수, 즉 00부터 n−1n-1까지의 순열입니다.

출력

각 테스트 케이스마다, 해당 순열이 반산술 순열이면 yes, 아니면 no 를 한 줄에 출력하세요.

예제5

  1. 예제 1

    입력
    3: 0 2 1 
5: 2 0 1 3 4
6: 2 4 3 5 0 1
0
    예상 출력
    yes
no
yes

  2. 예제 2

    입력
    3: 0 1 2
0
    예상 출력
    no

  3. 예제 3

    입력
    3: 1 0 2
0
    예상 출력
    yes

  4. 예제 4

    입력
    4: 0 2 1 3
4: 0 1 2 3
7: 0 4 2 6 1 5 3
3: 1 0 2
0
    예상 출력
    yes
no
yes
yes

  5. 예제 5

    입력
    3: 0 1 2
3: 0 2 1
3: 1 0 2
3: 1 2 0
3: 2 0 1
3: 2 1 0
0
    예상 출력
    no
yes
yes
yes
yes
no