32625번 - 분할

문제

크기 $N$의 정수 배열 $A$가 있다. 다음 조건을 만족하도록 배열을 연속 구간으로 분할하는 것이 가능한지 판단하시오.

• 배열의 모든 원소가 정확히 하나의 구간에 포함된다.
• 각 구간의 크기는 1ドル$ 이상 $N$ 미만이며, 모든 구간의 크기는 같다.
• 각 구간에서 최솟값과 최댓값을 더한 값이 모든 구간에서 같다.

입력

첫째 줄에 배열의 크기 $N$이 주어진다. $(2\leq N \leq 100,000円)$

둘째 줄에 $A$의 원소 $A_{1}, A_{2}, A_{3}, \cdots, A_{N}$이 공백으로 구분되어 주어진다. $(1\leq A_{i} \leq N)$

출력

조건을 만족하도록 배열을 분할하는 것이 가능하다면 1ドル$을, 그렇지 않다면 0ドル$을 첫째 줄에 출력한다.

제한

힌트