롱케이크 1

문제

비버중학교의 오늘 급식 메뉴는 롱케이크이다. 케이크는 1번부터 n번까지 n조각이 한 줄로 붙어 있고, 학생 n명이 한 줄로 서서 차례대로 원하는 조각 하나를 골라 가져간다.

가져가려는 조각이 다른 조각과 붙어 있으면 빵칼로 잘라내야 한다.

• 양옆이 모두 남아 있으면 2번 자른다.
• 한쪽만 남아 있으면 1번 자른다. (반대쪽은 케이크의 끝이거나 이미 가져간 자리)
• 양쪽 다 케이크의 끝이거나 이미 가져간 자리면 자르지 않는다.

학생들이 고른 조각 번호가 차례대로 주어질 때, 빵칼을 1번 사용하는 학생의 수와 2번 사용하는 학생의 수를 구해 보자.

예시

입력

6
2 5 1 6 4 3

출력

1 2

2번 조각(양옆 1, 3이 남아 있음)과 5번 조각(양옆 4, 6이 남아 있음)은 2번씩 자른다. 1번 조각은 왼쪽이 끝이고 오른쪽 2번은 이미 가져갔으므로 자르지 않고, 6번 조각도 마찬가지이다. 4번 조각은 왼쪽 3번만 남아 있어 1번 자른다. 3번 조각은 양옆이 모두 빈 자리라 자르지 않는다.

출처: SFPC 2023 도전 D1 (biko.kr 1637)