Вам дан массив \(b_1, b_2, \ldots, b_n\).
Некий анонимный информатор сообщил вам, что массив \(b\) был получен следующим образом: изначально существовал некоторый массив \(a_1, a_2, \ldots, a_n\), после чего \(k\) раз была произведена следующая двухкомпонентная операция:
- Была выбрана некоторая фиксированная точка\(^{\dagger}\) массива \(a\), пусть \(x\).
- После чего ровно \(x\) раз массив \(a\) был заменён на свой циклический сдвиг влево\(^{\ddagger}\).
И в результате \(k\) таких операций был получен массив \(b_1, b_2, \ldots, b_n\). Вы хотите проверить, могут ли слова анонимного информатора быть правдивы, или же он гарантированно лжёт.
\(^{\dagger}\)Число \(x\) называется фиксированной точкой массива \(a_1, a_2, \ldots, a_n\), если \(1 \leq x \leq n\) и \(a_x = x\).
\(^{\ddagger}\)Циклический сдвиг влево от массива \(a_1, a_2, \ldots, a_n\) это массив \(a_2, \ldots, a_n, a_1\).
Выходные данные
Для каждого набора входных данных выведите «Yes», если слова анонимного информатора могут быть правдой, и «No», если он гарантированно лжёт.
Примечание
В первом наборе входных данных массив \(a\) мог быть равен \([3, 2, 3, 4, 3]\). В первой операции была выбрана фиксированная точка \(x = 2\), и после \(2\) сдвигов влево массив принял вид \([3, 4, 3, 3, 2]\). Во второй операции была выбрана фиксированная точка \(x = 3\), и после \(3\) сдвигов влево массив принял вид \([3, 2, 3, 4, 3]\). В третьей же операции была выбрана фиксированная точка \(x = 3\), и после \(3\) сдвигов влево массив принял вид \([4, 3, 3, 2, 3]\), чему и равняется массив \(b\).
Во втором наборе входных данных массив \(a\) мог быть равен \([7, 2, 1]\). После операции с фиксированной точкой \(x = 2\) массив принял вид \([1, 7, 2]\). Далее после операции с фиксированной точкой \(x = 1\) массив снова принял изначальный вид \([7, 2, 1]\). Далее эти же \(2\) операции (с \(x = 2\) и \(x = 1\)) были повторены \(49\) раз. И итого после \(100\) операций массив снова принял вид \([7, 2, 1]\).
В третьем наборе входных данных нетрудно показать, что ответа нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 3
4 3 3 2 3
3 100
7 2 1
5 5
6 1 1 1 1
1 1000000000
1
8 48
9 10 11 12 13 14 15 8
2 1
1 42
|
Yes
Yes
No
Yes
Yes
No
|