일반물리학 수업의 주제 발표를 앞두고 명의 학생이 발표 연습을 하려고 한다. 학생들은 왼쪽에서 오른쪽으로 나란히 서 있으며, 모든 학생은 동시에 발표 연습을 시작한다.
각 학생이 발표를 진행하는 방법은 두 가지로, 빠르게 혹은 느리게 진행할 수 있다. 왼쪽에서 번째 학생이 발표를 빠르게 진행하면 발표를 마치는 데 의 시간이, 느리게 진행하면 의 시간이 걸린다.
선생님은 왼쪽에 있는 학생부터 차례대로 발표가 끝나기를 원한다. 즉, 왼쪽에서 번째 학생의 발표 시간을 라고 할 때, 이상 이하의 모든 양의 정수 에 대하여 을 만족해야 한다.
발표 연습을 시작하기 전에 선생님은 서로 인접한 두 학생의 위치를 정확히 한 번 교환한다.
왼쪽에서 번째 학생과 번째의 학생의 위치를 교환한 뒤, 각 학생의 발표 방식을 적절히 선택하여 왼쪽 학생부터 차례대로 발표를 끝내게 할 수 있다면, 이 교환을 좋은 교환이라고 하자. 가능한 좋은 교환의 개수를 구하여라.
첫 번째 줄에 학생의 수 이 주어진다.
두 번째 줄에 개의 양의 정수 이 공백으로 구분되어 주어진다.
문제의 정답을 출력한다.
세 번째 줄에 개의 양의 정수 이 공백으로 구분되어 주어진다.
