ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Regional School Programming Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Searching for the Truth

Time limit: 1.0 second
Memory limit: 64 MB
The Supreme Council of Magicians has been studying the recently found biography of Lich Sandro for many days. At present they are investigating a mystic numerical sequence written on one of the pages. Most of the magicians think that this sequence defines an algorithm for finding the Great Dodecahedron.
As you remember, the Great Dodecahedron is kept at the Temple of Five Polyhedra. Many magicians tried to get it but to no avail, because a protection spell is put on the Dodecahedron.
There is a row of n pedestals in the fourth hall of the Temple. The pedestals are numbered from left to right starting from 1. The Great Dodecahedron is mounted on one of the pedestals, and the other pedestals support its exact copies, which have no magical power.
If a magician touches the real Dodecahedron, all the copies will disappear at once. If a magician touches a copy, nothing will happen, but, as soon as he removes the hand, the Dodecahedron will shift to a neighboring left or right pedestal and a copy will appear in its place.
The Supreme Council of Magicians assumes that the numbers in the sequence correspond to the numbers of pedestals and define the order in which the dodecahedra should be touched. Help the Council verify that this algorithm can actually be used to find the artifact regardless of its initial position and for any of its admissible transitions.


The first line contains the number n of pedestals and the number m of integers in the sequence (2 ≤ n, m ≤ 100000). The sequence itself is given in the second line, which contains m positive integers not exceeding n.


Output “YES” if the sequence defines a correct algorithm for finding the Great Dodecahedron and “NO” otherwise.


3 2
2 2
3 3
1 2 3
Problem Author: Mikhail Rubinchik
Problem Source: Ural Regional School Programming Contest 2010
To submit the solution for this problem go to the Problem set: 1790. Searching for the Truth