쉬는 시간, 하윤이는 길이 의 순열 을 여러 개의 레고 블록으로 나누려고 한다.
길이 의 순열이란 이상 이하의 정수가 각각 정확히 한 번씩 등장하는 수열이다. 각 블록은 순열에서 연속한 하나 이상의 원소로 이루어지며, 블록의 순서는 원래 순열에서의 순서를 따른다.
하윤이는 다음 조건을 모두 만족하도록 순열을 나누려고 한다.
예를 들어 이라면 , , 의 세 블록으로 나눌 수 있다.
조건을 만족하면서 만들 수 있는 블록 개수의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 조건을 만족하면서 순열을 나누어 얻을 수 있는 블록 개수의 최댓값을 출력한다.
, , 의 세 블록으로 나누면 조건을 만족한다. 네 개 이상의 블록으로 나누는 것은 불가능하므로 답은 이다.
두 개 이상의 블록으로 나누는 방법이 없으므로 전체 순열을 하나의 블록으로 사용해야 한다.
