362. Detecting Circular Loops in an Array

0

Medium

Krishna, an avid nature enthusiast, enjoys exploring the meandering forest trails in his town. However, he often loses his way and struggles to find his way back to the starting point. To overcome this challenge, Krishna utilizes an array of positive and negative integers. Whenever he encounters a positive integer k at index i, he moves forward k steps. Conversely, if he encounters a negative integer (-k), he moves backward k steps.

One day, Krishna found himself lost in the forest and was unable to locate his way back to the starting point. He pondered if there was a way to detect a cycle in the array that would assist him in finding his way back. This cycle would begin and end at the same index and consist solely of either forward or backward movements.

##### Krishna's Program

Krishna decided to develop a program that could identify such a cycle, taking into consideration that the array was circular, meaning that the next element after the last element was the first element, and the previous element before the first element was the last element.

Krishna's program needed to determine if there existed a cycle in the array that satisfied the following conditions:

• The cycle started and ended at the same index.
• The cycle's length was greater than 1.
• All movements in the cycle followed a single direction, either forward or backward.

If such a cycle existed, Krishna's program had to return 1. Otherwise, it had to return 0.

Could you assist Krishna in writing this program?

Input Format

The first line contains a single integer n. The second line contains n space-separated integers.

Output Format

A single digit, either 1 or 0.

Example

Input

5 2 -1 1 2 2

Output

1

Constraints

1<=n<=1e6
-1000<=Ai<=1000