На этой неделе на уроках информатики васе рассказывают про строки.

вчера вася узнал, что такое циклический сдвиг:

k-й циклический сдвиг строки – это строка, полученная перестановкой первых k символов строки в её конец. в частности, 0-й циклический сдвиг строки – это сама строка.

и он написал программу, которая умеет перемещать первый символ строки в её конец k раз, получая таким образом k-й циклический сдвиг строки.

сегодня васе нужно реализовать разворот строки. но у васи тренировка. ему некогда писать новые сложные программы. поэтому он задался вопросом:

можно ли циклическими сдвигами развернуть строку?

своим друзьям вася узнал, на какой строке (да, всего одной) будет тестировать его программу учитель, у которого нет времени рецензировать код каждого ученика. поэтому вопрос :

можно ли циклическими сдвигами развернуть строку s?

ему ответить на этот вопрос.

формат входных данных

первая строка содержит одно целое число n (1≤n≤3⋅105) – длина строки s.

во второй строке – сама строка s, на которой будет тестировать программу васи учитель. состоит строка s только из строчных латинских букв.

формат выходных данных

если строку нельзя развернуть циклическими сдвигами, то выведите число −1. в противном случае выведите такое целое число k (0≤k
пояснение к примеру

0-й циклический сдвиг строки s равен abac.

1-й циклический сдвиг строки s равен baca.

2-й циклический сдвиг строки s равен acab.

3-й циклический сдвиг строки s равен caba.

развёрнутая строка s равна caba.

единственное подходящее k равно трём.

sample input:

4
abac
sample output:

3
напишите программу. тестируется через stdin → stdout
time limit: 3 секунды
memory limit: 256 mb

lilia25021    3   17.10.2019 11:23    5