Kicksort

Kickstart의 우리는 잘 알려진 Quicksort 알고리즘을 좋아한다. 이 알고리즘은 목록에서 피벗 값을 하나 선택하고, 피벗 값과 비교한 결과에 따라 나머지 각 값을 두 개의 새 목록 중 하나로 옮긴 다음, 그 새 목록들을 각각 재귀적으로 정렬한다. 그러나 이 알고리즘은 나머지 값이 모두 두 새 목록 중 하나에만 들어가게 하는 피벗을 선택할 수도 있으며, 이는 분할 정복 전략의 취지를 무색하게 한다. 이러한 피벗을 최악의 경우 피벗이라고 부른다.

이 문제를 피하고자 우리만의 변형인 Kicksort를 만들었다. 누군가 가운데에 있는 값을 피벗으로 사용하는 것이 좋다고 말해 주었으므로, 우리 알고리즘은 다음과 같이 동작한다.

Kicksort(A): // A is a 0-indexed list with E elements
    If E ≤ 1, return A.
    Otherwise:
      Create empty new lists B and C.
      Choose A[floor((E-1)/2)] as the pivot P.
      For i = 0 to E-1, except for i = floor((E-1)/2):
        If A[i] ≤ P, append it to B.
        Otherwise, append it to C.
    Return the list Kicksort(B) + [P] + Kicksort(C).
    // [P] is a new list with just P; + means concatenate

연습을 위해, 1부터 N까지의 수로 이루어진 순열인 목록에 Kicksort를 시험하고 있다. 안타깝게도 Kicksort에도 Quicksort와 같은 문제가 여전히 있는 듯하다. 모든 피벗이 최악의 경우 피벗이 되는 것이 가능하다!

예를 들어 목록 1 4 3 2을 생각해 보자. Kicksort는 4을 피벗으로 선택하며, 나머지 값 1 3 2는 모두 두 새 목록 중 하나에 들어간다. 그런 다음 Kicksort가 그 목록 1 3 2에 대해 호출되면 3을 선택하고, 다시 한번 나머지 값이 모두 두 새 목록 중 하나에 들어간다. 마지막으로 목록 1 2에서 1을 선택하며, 나머지 값 2는 당연히 두 새 목록 중 하나에만 들어간다. 모든 경우에 알고리즘은 최악의 경우 피벗을 선택한다. (Kicksort가 원소가 0개 또는 1개인 목록에 대해 호출되면 피벗을 전혀 선택하지 않는다는 점에 유의하라.)

이를 더 조사할 수 있도록 도와 달라! 1부터 N까지의 수로 이루어진 순열이 주어질 때, Kicksort가 최악의 경우 피벗만 선택할지 판별하라.

제한

메모리 제한: 1GB. 값 $A_{i}$는 1부터 N까지의 값으로 이루어진 순열이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 32. 시간 제한: 20초. 2 ≤ N ≤ 4.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 100. 시간 제한: 200초. 2 ≤ N ≤ 10000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 순열의 원소 수를 나타내는 정수 N 하나가 주어진다. 둘째 줄에는 1부터 N까지의 값으로 이루어진 순열인 N개의 정수 $A_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 이 목록을 정렬할 때 Kicksort가 최악의 경우 피벗만 선택한다면 YES, 그렇지 않다면 NO이다.

예제 케이스 #1은 문제 설명에서 다룬 경우이다.

예제 케이스 #2에서 첫 피벗은 1이며, 나머지 값 2 3 4가 모두 두 새 목록 중 하나에 들어가게 하므로 최악의 경우 피벗이다. 그러나 목록 2 3 4에 대한 Kicksort 호출은 3을 피벗으로 선택한다. 이는 2를 새 목록 중 하나에 넣고 4을 다른 목록에 넣으므로 최악의 경우 피벗이 아니다.

예제 케이스 #3에서 Kicksort는 최악의 경우 피벗 2을 선택하며 시작하고, 그 뒤에는 선택할 피벗이 없다.

예제 케이스 #4에서 Kicksort는 최악의 경우 피벗이 아닌 2을 선택하며 시작한다.