Синдзю очень любит перестановки! Сегодня она взяла перестановку \(p\) у Дзюдзю, чтобы поиграть с ней.
\(i\)-й циклический сдвиг перестановки \(p\) — это такое преобразование, что перестановка \(p = [p_1, p_2, \ldots, p_n] \) становится равной \( p = [p_{n-i+1}, \ldots, p_n, p_1,p_2, \ldots, p_{n-i}]\).
Назовём мощностью перестановки \(p\) количество различных элементов в массиве префиксных максимумов \(b\). Массив префиксных максимумов \(b\) — это массив длины \(n\), в котором \(b_i = \max(p_1, p_2, \ldots, p_i)\). Например, мощность перестановки \([1, 2, 5, 4, 6, 3]\) равна \(4\), так как \(b=[1,2,5,5,6,6]\) и в \(b\) всего \(4\) различных элемента.
К сожалению, Синдзю потеряла перестановку \(p\)! Вся информация, которую она помнит — это массив \(c\), где \(c_i\) равно мощности \((i-1)\)-го циклического сдвига перестановки \(p\). Она не уверена, что запомнила всё правильно, теперь она хочет проверить свою память.
Задан массив \(c\), определите, существует ли такая перестановка \(p\), которая согласуется с заданным массивом \(c\). Вам не нужно находить саму перестановку \(p\).
Перестановка — это массив из \(n\) различных целых чисел от \(1\) до \(n\), которые записаны в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) перестановкой не является (\(2\) содержится дважды). Аналогично, \([1,3, 4]\) тоже не является перестановкой (\(n=3\), но массив содержит значение \(4\)).
Выходные данные
Для каждого набора входных выведите «YES», если существует перестановка \(p\), согласующаяся с заданным массивом \(c\). Выведите «NO» в противном случае.
Вы можете использовать любой регистр букв при выводе «YES» и «NO» (например, строки «yEs», «yes», «Yes» и «YES» будут расценены как положительный ответ).
Примечание
В первом наборе входных данных примера перестановка \([1]\) согласуется с заданным массивом \(c\).
Во втором наборе входных данных примера перестановка \([2,1]\) согласуется с заданным массивом \(c\).
В пятом наборе входных данных примера перестановка \([5,1,2,4,6,3]\) согласуется с заданным массивом \(c\), так как:
- нулевой циклический сдвиг перестановки \(p\) — это \([5, 1, 2, 4, 6, 3]\). Мощность этого сдвига равна \(2\), так как \(b = [5, 5, 5, 5, 6, 6]\), в этом массиве только \(2\) различных элемента: \(5\) и \(6\).
- первый циклический сдвиг перестановки \(p\) это \([3, 5, 1, 2, 4, 6]\). Мощность этого сдвига равна \(3\), так как \(b=[3,5,5,5,5,6]\).
- второй циклический сдвиг перестановки \(p\) это \([6, 3, 5, 1, 2, 4]\). Мощность этого сдвига равна \(1\), так как \(b=[6,6,6,6,6,6]\).
- третий циклический сдвиг перестановки \(p\) это \([4, 6, 3, 5, 1, 2]\). Мощность этого сдвига равна \(2\), так как \(b=[4,6,6,6,6,6]\).
- четвёртый циклический сдвиг перестановки \(p\) это \([2, 4, 6, 3, 5, 1]\). Мощность этого сдвига равна \(3\), так как \(b = [2, 4, 6, 6, 6, 6]\).
- пятый циклический сдвиг перестановки \(p\) это \([1, 2, 4, 6, 3, 5]\). Мощность этого сдвига равна \(4\), так как \(b = [1, 2, 4, 6, 6, 6]\).
Таким образом, для этой перестановки \(c = [2, 3, 1, 2, 3, 4]\).
В третьем, четвёртом и шестом наборах входных данных примера можно показать, что искомой перестановки, которая согласуется с \(c\), не существует.