Vova has won $n$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of trophies.

The second line contains $n$ characters, each of them is either G or S. If the $i$-th character is G, then the $i$-th trophy is a golden one, otherwise it's a silver trophy. 


-----Output-----

Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.


-----Examples-----
Input
10
GGGSGGGSGG

Output
7

Input
4
GGGG

Output
4

Input
3
SSS

Output
0



-----Note-----

In the first example Vova has to swap trophies with indices $4$ and $10$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $7$. 

In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $4$. 

In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $0$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
A = input()
x = A.count('G')
num_1 = 0
num_2 = 0
max_num = 0
flag = 0
for i in range(n):
    if A[i] == 'G' and flag == 0:
        num_1 += 1
    elif A[i] == 'G' and flag == 1:
        num_2 += 1
    elif A[i] == 'S' and flag == 0:
        flag = 1
    else:
        if num_1 + num_2 + 1 <= x:
            if num_1 + num_2 + 1 > max_num:
                max_num = num_1 + num_2 + 1
            num_1 = num_2
            num_2 = 0
            flag = 1
        else:
            if num_2 + num_1 > max_num:
                max_num = num_1 + num_2
            num_1 = num_2
            num_2 = 0
            flag = 1
if num_1 + num_2 + 1 <= x:
    if num_1 + num_2 + 1 > max_num:
        max_num = num_1 + num_2 + 1
else:
    if num_2 + num_1 > max_num:
        max_num = num_1 + num_2
print(max_num)


n = int(input())
s = input()


max_ans = len([x for x in s if x == 'G'])
right = 0
cnt = 0
ans = 0
for i in range(n):
	assigned = False
	for j in range(right, n, 1):
		if s[j] == 'S':
			cnt += 1
		if cnt > 1:
			right = j
			cnt -= 1
			assigned = True
			break
	if not assigned:
		right = n
	# print(i, right)
	ans = max(ans, right - i)
	if s[i] == 'S':
		cnt -= 1
ans = min(ans, max_ans)
print(ans)

input()
res = 0
cur = 1
cur_p = 0
s = input()
for c in s:
	if c == "G":
		cur += 1
		cur_p += 1
		res = max(res, cur)
	else:
		cur = cur_p + 1
		cur_p = 0
print(min(res, s.count("G")))


n=int(input())
t=input()
L=[-1]
s=0
for i in range(n):
    if t[i]=='S':
        L.append(i)
        s+=1
L.append(n)
m = L[1]-L[0]-1
for i in range(len(L)-2):
    if L[i+2]-L[i]-1 > m:
        m=L[i+2]-L[i]-1
print(min(m,n-s))


n = int(input())
ks  =input().strip()

prev_g_seq_len = 0
cur__g_seq_len = 0
prev_is_s = True

res = 0
for j in ks:
    if j == 'S':
        prev_g_seq_len = cur__g_seq_len
        cur__g_seq_len = 0
        # prev_is_s = True
    else:
        cur__g_seq_len += 1
        # prev_is_s = False
    res = max (res, prev_g_seq_len + cur__g_seq_len + 1)

mmm = ks.count('G')
res = min(mmm, res)




print(res)




n = int(input())
s = input()
g1 = 0
g2 = 0
ans = 0
num2 = s.count("G")
for  i in range(n):
    if s[i] == "G":
        g1 += 1
    else:
        g2 = g1
        g1 = 0
        
    num = g1  + g2
    if num2 != num:
        num+=1
    ans = max(ans,num)
print(min(n,ans))

def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n = ii()
s = input().strip()

g = []
i = 0
lng = 0
while i < n:
    if s[i] == 'S':
        i += 1
        continue
    j = i + 1
    while j < n and s[j] == 'G':
        j += 1
    g.append((i, j))
    lng = max(lng, j - i)
    i = j + 1

if not g:
    ans = 0
elif len(g) == 1:
    ans = lng
else:
    extra = len(g) > 2
    ans = lng + 1
    for i in range(len(g) - 1):
        s, e = g[i]
        s2, e2 = g[i + 1]
        if s2 != e + 1:
            continue
        ans = max(ans, e - s + e2 - s2 + extra)
print(ans)


n = int(input())
s = input()

golden_sub = s.split('S')
nG = 0
for c in s:
	if c == 'G':
		nG += 1

t = len(golden_sub)
if t == 1:
	print(len(golden_sub[0]))
else:
	ans = 0
	for i in range(t - 1):
		l1 = len(golden_sub[i])
		l2 = len(golden_sub[i + 1])
		if l1 + l2 < nG:
			ans = max(ans, l1 + l2 + 1)
		else:
			ans = max(ans, l1 + l2)
	print(ans)


from itertools import groupby as gb
n = int(input())
s = input()
g = gb(s)
gl = []
for k,v in g:
    gl.append([k,len(list(v))])
l = len(gl)

if s[0]=='S':
    if l==1:
        print(0)
        return
    elif l<=3:
        print(gl[1][1])
        return
if s[0]=='G':
    if l<=2:
        print(gl[0][1])
        return

res = 0
# 1
for i,[k,v] in enumerate(gl):
    if (k,v) == ('S',1) and i not in (0,l-1):
        if s[0]=='S' and l<=5:
            res = max(res, gl[i-1][1]+gl[i+1][1])
        elif s[0]=='G' and l<=4:
            res = max(res, gl[i-1][1]+gl[i+1][1])
        else:
            res = max(res, gl[i-1][1]+gl[i+1][1] + 1)
# 2
for i,[k,v] in enumerate(gl):
    if (k) == ('S') and v > 1:
        if i != 0:
            res = max(res, gl[i-1][1] + 1)
        if i != l-1:
            res = max(res, gl[i+1][1] + 1)
print(res)


n=int(input())
s=str(input())
last_seq=0
curr_seq=0
ans=0
gcount=0
i=0
while i<n-1:
    if s[i]=='G':
        gcount+=1
        curr_seq+=1
        i+=1
    else:
        if curr_seq+last_seq>ans:
            ans=curr_seq+last_seq
        if s[i+1]=='G':
            #gcount+=1
            last_seq=curr_seq
            curr_seq=0
            i+=1
        else:
            if curr_seq>ans:
                ans=curr_seq
            curr_seq=0
            last_seq=0
            i+=2
if s[-1]=='G':
    gcount+=1
    curr_seq+=1
if curr_seq+last_seq>ans:
    ans=curr_seq+last_seq
#print(gcount,ans)
if gcount>ans:
    print(ans+1)
else:
    print(ans)


n = int(input())
seq = input().replace(' ', '')
nGTotal = seq.count('G')
nGCur = 0
right = -1
result = 0
for left in range(n):
    if right < left:
        right = left - 1
        nGCur = 0
    while right + 1 < n and ((seq[right + 1] == 'G' and (right - left + 1 - nGCur == 0 or nGCur + 2 <= nGTotal)) or (seq[right + 1] == 'S' and right + 1 - left + 1 - nGCur <= 1 and nGCur + 1 <= nGTotal)):
        right += 1
        if seq[right] == 'G':
            nGCur += 1
    result = max(right - left + 1, result)
    if seq[left] == 'G':
        assert right >= left
        nGCur -= 1
print(result)


n=int(input())
s=input()
a=[]
k=1
for i in range(n-1):
    if s[i]=='G' and s[i+1]=='G':
        k+=1
    elif s[i]=='G' and s[i+1]=='S':
        a.append([i,k])
        k=1
if s[-1]=='G':
    a.append([n-1,k])
if len(a)==0:
    print(0)
elif len(a)==1:
    print(a[0][1])
elif len(a)==2:
    ma=0
    for i in a:
        ma=max(i[1],ma)
    ka=0
    for i in range(len(a)-1):
        if (a[i+1][0]-a[i+1][1]+1)-a[i][0]==2:
            ka=max(a[i][1]+a[i+1][1],ka)
    if ka>ma+1:
        print(ka)
    else:
        print(ma+1)
else:
    ma=0
    for i in a:
        ma=max(i[1],ma)
    ka=0
    for i in range(len(a)-1):
        if (a[i+1][0]-a[i+1][1]+1)-a[i][0]==2:
            ka=max(a[i][1]+a[i+1][1],ka)
    print(max(ka,ma)+1)


x = int(input())
s = input()

cnts = s.count('S')
cntg = s.count('G')
cnt=0
mx2 = -55
for i in range(len(s)-1):
	if(s[i]=='G' and s[i+1]=='G'):
		cnt+=1
	else:
		cnt=0
	mx2 = max(cnt, mx2)

mx2+=1

ls=[]
s+="0"
s='0'+s
for i in range(1, len(s)):
	if(s[i-1]=='G' and s[i]=='S' and s[i+1]=='G'):
		ls.append(i)


cnt = 0
mx=-55
for i in range(len(ls)):
	c = ls[i]-1
	while(s[c]=='G'):
		cnt+=1
		c-=1
	c = ls[i]+1
	while(s[c]=='G'):
		cnt+=1
		c+=1
	mx = max(cnt, mx)
	cnt=0

maxx = max(mx, mx2)
if(cntg==0):
	print(0)
elif(cntg>maxx and cnts>0):
	print(maxx+1)
else:
	print(maxx)

n = int(input())
s = input()
max = 0
l = 0
has_s = False
gs = 0
for r in range(n):
    if s[r] == 'G':
        gs += 1
    else:
        if not has_s:
            has_s = True
        else:
            while s[l] == 'G':
                l += 1
            l += 1
    if r-l+1 > max:
        max = r-l+1
ans = max
if gs < max:
    ans -= 1

print(ans)

n = int( input() )
s = input() + 'SS'

d = []
silv = 0
gold = 0
l = []
for c in s:
    if c == 'G':
        gold += 1
        silv = 0
    else:
        silv += 1
        if silv > 1 and len( l ) > 0:
            d.append(l)
            l = []
        if gold > 0:
            l.append( gold )
        gold = 0



if len( d ) == 0:
    print( 0 )
elif len( d ) == 1:
    l = d[ 0 ]
    if len( l ) == 1 :
        print( l[ 0 ] )
    elif len( l ) == 2:
        print( sum( l ) )
    else:
        m = 0
        last = 0
        for i in l:
            m = max(m, last + i + 1 )
            last = i
        print( m )
else:
    m = 0
    for l in d:
        last = 0
        for i in l:
            m = max(m, last + i + 1 )
            last = i
    print( m )


import sys
from math import ceil, sqrt

input = sys.stdin.readline

n = int(input())
s = input().strip()

last = "S"
ans = []
count = 0
freq = {'S': 0, 'G': 0}

for i in range(n):
    freq[s[i]] += 1
    if s[i] != last:
        ans.append((count, last))
        last = s[i]
        count = 1
    else:
        count += 1
ans.append((count, last))
ans.pop(0)

if freq['G'] == 0:
    print(0)
    return

final = max([x[0] for x in ans if x[1] == 'G'])
if freq['G'] > final:
    final += 1

for i in range(len(ans) - 2):
    if ans[i][1] == 'G' and ans[i+1][1] == 'S' and ans[i+1][0] == 1 and ans[i+2][1] == 'G':
        if freq['G'] > ans[i][0] + ans[i+2][0]:
            final = max(final, ans[i][0] + ans[i+2][0] + 1)
        else:
            final = max(final, ans[i][0] + ans[i+2][0])
print(final)

n=int(input())
s=input()
a=[0]*100005
ans,maxn=0,0

for i in range(0,n):
    if(s[i]=='G'):
        if i==0:
            a[0]=1
        else:
            a[i]=a[i-1]+1
        maxn=max(maxn,a[i])
        ans+=1
for i in range(n-2,-1,-1):
    if (s[i] == 'G'):
        a[i]=max(a[i],a[i+1])
for i in range(0,n):
    if(i>0 and i <n-1 and s[i]=='S' and s[i-1]=='G'and s[i+1]=='G'and a[i-1]+a[i+1]!=ans):
        maxn=max(maxn,a[i-1]+a[i+1]+1)
        continue
    if (i > 0 and i < n - 1 and s[i] == 'S' and s[i - 1] == 'G' and s[i + 1] == 'G'):
        maxn = max(maxn, a[i - 1] + a[i + 1])
        continue
    if(s[i]=='G' and a[i]!=ans):
        maxn=max(maxn,a[i]+1)
print(maxn)

3.5

N = int(input())
A = input()

L = []
cpt = 1
ret = 0

for i in range(1, len(A)):
    if A[i] == A[i-1]:
        cpt += 1
    else:
        L.append(cpt)
        if A[i] == "S":
            ret = max(ret, cpt)
            
        cpt = 1

L.append(cpt)
if A[-1] == "G":
    ret = max(ret, cpt)

if ret == 0:
    print("0")
    return

if A[0] == "G":
    cur = True
else:
    cur = False

for i in range(0, len(L)):
    if not cur:
        if L[i] == 1 and (i+3 < len(L) or i-3 >= 0):
            new = 1
            if i > 0:
                new += L[i-1]
            if i < len(L)-1:
                new += L[i+1]

            ret = max(ret, new)

        if L[i] == 1 and i > 0 and i < len(L)-1:
            ret = max(ret, L[i-1] + L[i+1])
                
        if i > 0 and i+1 < len(L):
            ret = max(ret, L[i-1]+1)

        if i < len(L)-1 and i-1 >= 0:
            ret = max(ret, L[i+1]+1)
    
    cur = not cur

print(ret)


def solve():
    n = int(input())
    s = input()
    l = []
    g_seg, s_seg = 0, 0
    g_count = 0
    for i in range(n):
        if s[i] == 'S':
            if g_seg:
                g_count += 1
                l.append(("G", g_seg))
                g_seg = 0
            s_seg += 1
        else:
            if s_seg:
                l.append(("S", s_seg))
                s_seg = 0
            g_seg += 1
    if g_seg:
        l.append(("G", g_seg))
        g_count += 1
    # print(l)
    if not g_count:
        return 0
    if len(l) == 1:
        return l[0][1]
    elif len(l) == 2:
        return l[1][1]
    if g_count == 2:
        ans = 0
        for i in range(len(l) - 2):
            if l[i][0] == 'G':
                if l[i + 1][1] == 1:
                    ans = max(ans, l[i][1] + l[i + 2][1])
                else:
                    ans = max(ans, l[i][1] + 1, l[i + 2][1] + 1)
        return ans
    else:
        ans = 0
        for i in range(len(l) - 2):
            if l[i][0] == 'G':
                if l[i + 1][1] == 1:
                    ans = max(ans, l[i][1] + 1 + l[i + 2][1])
                else:
                    ans = max(ans, l[i][1] + 1, l[i + 2][1] + 1)
        return ans


print(solve())

n=int(input())
s=input()
ans=0
sc,gc,pi,ci=0,0,-1,-1
for i in range(1,n+1):
	if s[i-1]=='G':
		gc+=1
	else:
		sc+=1
		if pi==-1:
			ans=max(ans,i-1)
		else:
			ans=max(ans,i-1-pi)
		pi=ci
		ci=i
	#print(ans)
#print(gc,sc)
if sc==1:
	print(n-1)
	return
if sc==2 and (s[0]=='S' or s[n-1]=='S'):
	print(n-2)
	return

if pi==-1:
	ans=max(ans,n)
else:
	ans = max(ans,n-pi)

print(min(ans,gc))


#!/usr/bin/env python
# coding: utf-8

# In[ ]:



import math


# In[5]:


n=int(input())
data= list(input())


# In[21]:


firstsilver=-1
secondsilver=-1
mdiff=[-1,-1,-1]

for i in range(0,n):
    if data[i]=='S' and secondsilver==-1:
        secondsilver=i
    elif data[i]=="S":
        firstsilver=secondsilver
        secondsilver=i
    diff=i-firstsilver
    if diff>mdiff[0]:
        mdiff=[diff,firstsilver,i,secondsilver]

#print(mdiff)        
        


# In[22]:

if mdiff[1]==mdiff[3]:
    penalty=0
else:
    penalty=1
    
for i in range(0,n):
    if i not in list(range(mdiff[1]+1,mdiff[2]+1)):
        if data[i]=='G':
            penalty=0


# In[23]:


print(mdiff[0]-penalty)


# In[ ]:


def longestSubSeg(a, n):
    cnt0 = 0
    l = 0
    max_len = 0;
    ctG=0
    # i decides current ending point
    for i in range(0, n):
        if a[i] == 'S':
            cnt0 += 1
        if a[i] =='G':
            ctG+=1
        while (cnt0 > 1):
            if a[l] == 'S':
                cnt0 -= 1
            l += 1

        max_len = max(max_len, i - l + 1);
    if max_len>ctG:
        return max_len-1
    return max_len
n=int(input())
a=list(input())
print(longestSubSeg(a,n))

def mi():
	return list(map(int, input().split()))
'''
10
GGGSGGGSGG
'''
n = int(input())
s = list(input())
for i in range(n):
	if s[i]=='G':
		s[i] = 1
	else:
		s[i] = 0
a = []
i = 0
while i<n:
	if s[i]==1:
		c = 0
		zc = 0
		pz = -1
		while i<n and zc <=1:
			if s[i]==1:
				c+=1
			else:
				zc+=1
				if zc==1:
					pz = i
			i+=1
		a.append(c)
		if pz!=-1:
			i = pz
	else:
		i+=1
if len(a)>1:
	ans = max(a)+1
	if ans>s.count(1):
		print(s.count(1))
	else:
		print(max(a)+1)
elif len(a)==1:
	print(a[0])
else:
	print(0)


n =int(input())
cups = input()

def maxlength(cups):
    length = 0
    for i in cups:
        if i == 'G':
            length =  length + 1
    return length
  
ll = cups.split('S')
themax = maxlength(cups)
maxl = 0
length =0
for i in range(len(ll)):
    if len(ll[i])>0 and length > 0:
        length = len(ll[i]) + length
        if length >maxl :
            maxl = length
        length = len(ll[i])
    if length == 0 or len(ll[i]) ==0:
        length = len(ll[i])
    if length> maxl and length<=themax:
        maxl = length
if maxl < themax:
    maxl  = maxl + 1
print(maxl)