Shake Sort는 두개의 변수를 활용하여 정렬을 진행합니다.

예를 통해서 설명하자면

low: 소트할 대상의 하단 위치

high: 소트할 대상의 상단 위치

• low : 1 , high : 5 이면 1 번째 ~ 5 번째가 소트할 대상
• low : 2, high : 4 이면 2 번째 ~ 4 번째가 소트할 대상 즉 1 번 , 5 번은 이미 정렬이 된 상태
• low >= high 이면 소트가 끝난 것을 의미

각 스텝에서 버블정렬과 원리가 같은 두번의 스캔이 일어납니다.

• 한 번은 아래에서 위로 ... 마지막으로 자리바꿈이 이루어진 위치를 high 변수로 재 지정
• 한 번은 위에서 아래로 ... 마지막으로 자리바꿈이 이루어진 위치를 low 변수로 재 지정
• low < high 참이면 반복

위와 같이 정렬이 끝날 때까지 최종 스텝의 수를 출력하는 프로그램을 작성하십시오.

입력

첫 줄에 데이터의 개수( 2 이상 1000 이하 )

다음 줄에 데이터 입력

출력

정렬이 끝날 때 까지 최종 스텝의 수