아래는 퀵 소트를 제안한 C. A. R. Hoare가 제시한 분할 알고리즘이다.

HOARE_PARTITION을 구현하시오.

HOARE-PARTITION(A, p, r)
1   x = A[p]
2   i = p - 1
3   j = r + 1
4   while TRUE
5       repeat
6           j = j - 1
7       until A[j] ≤ x
8       repeat
9           i = i + 1
10      until A[i] ≥ x
11      if i < j
12          exchange A[i] with A[j]
13      else return j

입력

• 첫 행은 배열이다.
• 둘째 행은 시작 인덱스(p)와 끝 인덱스(r)이다.

출력

• 입력 배열에 Hoare_partition을 적용한 후의 배열이다.

제한

• 1 ≤ n ≤ 10,000,000
• 0 ≤ p ≤ r ≤ n-1
• n은 배열에 담긴 요소의 개수이다.

예제 입력 1

9 21 2 18 7 1 3 5 6 4 10 12
5 11

예제 출력 1

9 21 2 18 7 1 3 5 6 4 10 12

예제 입력 2

9 21 2 18 7 1 3 5 6 4 10 12
2 9

예제 출력 2

9 21 1 18 7 2 3 5 6 4 10 12