Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Kingdom of Crisis

By TarifEzaz · Limits 1s, 512 MB

In a kingdom far away, NN people live in a circle of harmony. Literally, they have constructed a circular area and built their houses towards the periphery of it. For simplicity, we can assume that the kingdom is a circle and the houses are points on the circle's periphery.

Due to this scenario, a person living in that kingdom, can only interact with the two other neighbors who are adjacent to that person. When a person needs to make some money transaction, he can only do so with either the person on his right or with the person on his left.


Photo Credit: Hedning

Now, there is a huge economic crisis going on in the kingdom and the king has decided to equally divide the wealth across all the citizens. But the circular city only allows direct transaction between neighbors. Not just that, the king also ordered that a person can make at most one transaction with one of his neighbors.

So here's the deal, given the wealth of NN individuals and their relative positions, can you decide whether it would be possible to divide the money equally among all the people?

Input

The first line of the input will contain an integer NN (1N105)(1 \leq N \leq 10^5), the size of the population of the kingdom. The following NN lines will have one integer xix_i (1xi1091\leq x_i \leq 10^9) , where xix_i is the wealth of the i'th person. Since all the people of this kingdom are living in a circle, we have picked a position at some point of the circle and called it 11. Thus, 11 and NN are adjacent to each other.

Output

Output one line, Yes if it's possible to distribute the amount equally and No otherwise.

Sample

InputOutput
3
1
1
1
Yes

Since all of the citizens have equal amount, they already fulfill king's requirements.


    Discussion

    Statistics


    84% Solution Ratio

    aomine23Earliest, 8M ago

    ADRI0777Fastest, 0.0s

    ABID_JAWADLightest, 131 kB

    Jewel.SamaCShortest, 83B

    Submit

    Login to submit

    Editorial

    Since the kingdom is circular, we start from a person who has the highest money and move all the day...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.