A group of robotics students in Puerto Rico built an amateur radio receiver inspired by the legacy of the Arecibo Observatory. During their first experiment, they left the receiver on, pointing at a distant star, and recorded its activity for \(n\) consecutive days.

Each day, the students wrote a 1 in their logbook if the receiver picked up an electromagnetic energy pulse, and a 0 if there was only static or silence.

The team theorizes that they have captured a message from an extraterrestrial intelligence. For the signal to be considered "intelligent" and not just random space noise, the energy pulses must follow a strictly rhythmic pattern. That is, the number of days that pass between one pulse (1) and the next pulse (1) must always be exactly the same. If the distance between the pulses changes at any point, they will assume it is just random radiation.

Given the students' logbook, your task is to write a program that determines whether they have found an intelligent signal or not.

Input Specification

The first line contains an integer \(n\), the total number of days the recording lasted. The second line contains a sequence of length \(n\), composed only of the characters 0 and 1. Guarantee: It is guaranteed that the given sequence will always contain at least three 1s.

Output Specification

Print YES (in uppercase) if the distance between all consecutive 1s is constant. Print NO (in uppercase) if the distance varies at any point.

Subtasks

This problem is divided into three difficulty levels. Your program will receive partial points depending on the memory and time efficiency of your solution.

• Subtask 1 (30 points): \(3 \le N \le 1\,000\).

  • Time limit: 1.0 seconds. Memory limit: 256 MB.

• Subtask 2 (30 points): \(3 \le N \le 100\,000\).

  • Time limit: 1.0 seconds. Memory limit: 256 MB.

• Subtask 3 (40 points): \(3 \le N \le 10\,000\,000\).

  • Time limit: 1.0 seconds. Strict memory limit: 2 MB. (Judges' note: Be careful with trying to store the entire sequence in memory!)

Examples

Example 1 Input:

8
00111000

Output

YES

Example 2 Input:

7
1001011

Output

NO

Example 3 Input:

7
1010100

Output

YES

Source

Codeforces