755. Array has a circular loop or not ??

0

Medium

Krishna, a nature lover, loves to explore the winding forest trails in his town. However, he often loses his way and struggles to get back to the starting point. To overcome this problem, Krishna uses an array of positive and negative integers. Whenever he comes across a positive integer k at an index i, he moves forward k steps. Conversely, if he comes across a negative integer (-k), he moves backward k steps.

One day, Krishna found himself lost in the forest and was unable to find his way back to the starting point. He wondered if he could somehow detect a cycle in the array that would help him find his way back. This cycle would start and end at the same index and consist only of either forward or backward movements.

##### Krishna's Program

Krishna decided to write a program that could detect such a cycle, taking into account that the array was circular, meaning that the last element's next element was the first element, and the first element's previous element was the last element.

Krishna's program had to determine if there was a cycle in the array that met 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.

Can you help Krishna write this program?

Input Format

First Line Contains single integer n Second line contains n space separated integers

Output Format

single digit 1 or 0

Example

Input

5 2 -1 1 2 2

Output

1

Constraints

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