В некоторой стране $$$n + 1$$$ городов, пронумерованных от $$$0$$$ до $$$n$$$. $$$n$$$ дорог соединяют эти города, $$$i$$$-я дорога соединяет города $$$i - 1$$$ и $$$i$$$ ($$$i \in [1, n]$$$).
У каждой дороги есть направление. Направления задаются строкой из $$$n$$$ символов, каждый символ — либо L, либо R. Если $$$i$$$-й символ — L, то $$$i$$$-я дорога сначала направлена из города $$$i$$$ в город $$$i - 1$$$; иначе она направлена из города $$$i - 1$$$ в город $$$i$$$.
Путешественник хочет посетить как можно больше городов этой страны. Сначала он выбирает город, из которого начнет свое путешествие. Каждый день путешественник должен перейти из текущего города в соседний город по дороге, и он может перейти по дороге только в соответствии с ее направлением; то есть, если дорога направлена из города $$$i$$$ в город $$$i + 1$$$, он может перейти из города $$$i$$$ в город $$$i + 1$$$, но не из $$$i + 1$$$ в $$$i$$$. После того как путешественник перемещается в соседний город, все дороги меняют свое направление на противоположное. Если путешественник не может перейти в соседний город, он обязан закончить свое путешествие; также он может закончить путешествие в любой момент, в который захочет.
Цель путешественника — посетить как можно больше городов за одно путешествие (каждый город можно посетить любое количество раз, но только первое посещение считается). Для каждого города $$$i$$$ посчитайте максимальное количество городов, которое путешественник может посетить за одно путешествие, если оно начинается в городе $$$i$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк. В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). Во второй строке — последовательность $$$s$$$, состоящая из ровно $$$n$$$ символов, каждый из которых — L или R.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n + 1$$$ целое число. $$$i$$$-е число должно быть равно максимальному количеству городов, которое можно посетить за одно путешествие, если это путешествие начинается в $$$i$$$-м городе.
2 6 LRRRLL 3 LRL
1 3 2 3 1 3 2 1 4 1 4
Название |
---|