Sergei B., the young coach of Pokemons, has found the big house which consists of n flats ordered in a row from left to right. It is possible to enter each flat from the street. It is possible to go out from each flat. Also, each flat is connected with the flat to the left and the flat to the right. Flat number 1 is only connected with the flat number 2 and the flat number n is only connected with the flat number n - 1.

There is exactly one Pokemon of some type in each of these flats. Sergei B. asked residents of the house to let him enter their flats in order to catch Pokemons. After consulting the residents of the house decided to let Sergei B. enter one flat from the street, visit several flats and then go out from some flat. But they won't let him visit the same flat more than once. 

Sergei B. was very pleased, and now he wants to visit as few flats as possible in order to collect Pokemons of all types that appear in this house. Your task is to help him and determine this minimum number of flats he has to visit. 


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of flats in the house.

The second line contains the row s with the length n, it consists of uppercase and lowercase letters of English alphabet, the i-th letter equals the type of Pokemon, which is in the flat number i. 


-----Output-----

Print the minimum number of flats which Sergei B. should visit in order to catch Pokemons of all types which there are in the house. 


-----Examples-----
Input
3
AaA

Output
2

Input
7
bcAAcbc

Output
3

Input
6
aaBCCe

Output
5



-----Note-----

In the first test Sergei B. can begin, for example, from the flat number 1 and end in the flat number 2.

In the second test Sergei B. can begin, for example, from the flat number 4 and end in the flat number 6. 

In the third test Sergei B. must begin from the flat number 2 and end in the flat number 6.

Difficulty: interview

Starter code:

Solutions:
from collections import *
c=Counter()
ans=n=int(input())
s=input()
k=len(set(s))
i=j=t=0
while j<n:
    while len(c)<k and j<n: c[s[j]]+=1; j+=1
    while len(c)==k:
        if j-i<ans: ans=j-i
        c[s[i]]-=1
        if c[s[i]]==0: del c[s[i]]
        i+=1
    
print(ans)

n = int(input())
s = input()
def main(n, s):
 k = set()
 for i in range(n):
    k.add(s[i])
 v = len(k)
 h = dict()
 for i in k:
    h[i] = 0
 l = 0
 r = n
 while (l + 1 < r):
    m = (l + r) // 2
    f = False
    for i in h:
        h[i] = 0
    x = 0
    for i in range(m):
        h[s[i]] += 1
        if h[s[i]] == 1:
            x += 1
    if x == v:
        f = True
    else:
        for i in range(m, n):
            h[s[i - m]] -= 1
            if h[s[i - m]] == 0:
                x -= 1
            h[s[i]] += 1
            if h[s[i]] == 1:
                x += 1
            if x == v:
                f = True
                break
    if f:
        r = m
    else:
        l = m
 print(r)
main(n, s)
            
    


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

exi = [0 for i in range(52)]
def fill(x):
    if(x.islower()):
        exi[ord(x)-97] = 1
        return ord(x)-97
    else:
        exi[ord(x)-65+26] = 1
        return ord(x)-65+26
arr = []
for c in s:
    arr.append(fill(c))

now = [0 for i in range(52)]
def check():
    for i in range(52):
        if(exi[i]):
            if(exi[i]>now[i]):
                return 0
    return 1

first = 0
now[arr[first]] += 1
if(check()):
    print(1)
    return

min = n
for i in range(1,n):
    now[arr[i]] += 1
    for j in range(first,i):
        if(now[arr[j]]>1):
            first += 1
            now[arr[j]] -= 1
        else:
            break
    if(check()):
        leng = i - first + 1
        if(min>leng):
            min = leng
print(min)

from sys import stdin

def main():
        n=int(stdin.readline())
        ville=stdin.readline()
        minimum=n
        maisons={}
        nbType=0
        for maison in ville:
                if maison!="\n" and maison not in maisons:
                        maisons[maison]=0
                        nbType+=1
        nbZeros=nbType-1
        inf=0
        sup=0
        maisons[ville[0]]+=1
        while n>sup:
                if nbZeros==0:
                        minimum=min(minimum,sup-inf+1)
                        maisons[ville[inf]]-=1
                        if maisons[ville[inf]]==0:
                                nbZeros+=1
                        inf+=1

                else:
                        sup+=1
                        if n>sup:
                                maisons[ville[sup]]+=1
                                if maisons[ville[sup]]==1:
                                        nbZeros-=1
        print(minimum)
main()



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

q = len(set(s))

d = {}
count = 0

best = 999999999
j = 0
for i in range(n):
	if s[i] not in d:
		d[s[i]] = 0
		count += 1
	
	d[s[i]] += 1
	if count == q:
		while d[s[j]] > 1:
			d[s[j]] -= 1
			j += 1
		best = min(best, i - j + 1)

print(best)

n = int(input())
temp = input()
st=[c for c in temp]
temp=set(st)
nT=len(temp)
s={}
for i in temp:
	s[i]=0
currT=set()
i=0
j=0
minL=10**10
for i in range(len(st)):
	currT.add(st[i])
	s[st[i]]+=1
	while j<i and (s[st[j]]>1):
		s[st[j]]-=1
		j+=1
	if len(currT)==nT:
		minL=min(minL,i-j+1)

print(minL)

n  = int (input())
s = input()
t = set()
for i in range(n):
    t.add(ord(s[i]))
l = len(t)
o = dict()
p = 0
i = 0
while p < l:
    r = o.get(ord(s[i]), 0)
    if r == 0:
        o[ord(s[i])] = 1
        p += 1
    else:
        o[ord(s[i])] += 1
    i += 1
left = 0
minn = i - left
while True:
    if o[ord(s[left])] > 1:
        o[ord(s[left])] -= 1
        left += 1
        minn = min(minn, i - left)
    else:
        if i >= n:
            break
        o[ord(s[i])] += 1
        i += 1
print(minn)



def pro():
    n = int(input())
    s = input()
    l = 0
    r = 0
    p = len(set(s))
    m = 100001
    y = len(s)
    k = set(s[0])
    d = dict()
    d[s[0]] = d.get(s[0], 0) + 1
    while r < y:
            if len(k)<p:
                r += 1
                if r < y:
                    k.add(s[r])
                    d[s[r]] = d.get(s[r], 0) + 1
            else:
                m = min(m, r - l + 1)
                if d[s[l]] == 1:
                    d[s[l]] = 0
                    k.remove(s[l])
                else:
                    d[s[l]] -= 1
                l += 1

    print(m)
pro()


n = int(input())
s = input()
tCap = []
shortest = n
l = 0
for r in range(n):
    if s[r] not in tCap:
        tCap+= s[r]
        shortest = r-l+1
    else:
        while s[l] in s[l+1:r+1]:
            l+=1
        if r-l+1 < shortest:
            shortest = r-l+1
print(shortest)


def createdict():
  x={}
  for i in range(26):
    x[chr(ord('a')+i)]=i
  for i in range(26,52):
    x[chr(ord('A')+i-26)]=i
  return x

n=int(input().strip())
s=input().strip()
l=[[] for i in range(52)]
ts=set()
cs=set()
d=createdict()

for i in range(n):
  if s[i] not in ts:
    ts.add(s[i])
  l[d[s[i]]].append(i)

for end in range(n):  # start = 0
  if s[end] not in cs:
    cs.add(s[end])
  if ts&cs == ts:
    break

ans=end+1
flag=0

for start in range(1,n):
  c=s[start-1]
  while l[d[c]]:
    if l[d[c]][0]<start:
      del l[d[c]][0]
      if len(l[d[c]])==0:
        flag=1
    elif start<=l[d[c]][0]<=end:
      break
    else:
      end=l[d[c]][0]
      break
  if flag:
    break
  ans=min(ans,end-start+1)
  
print(ans)

from collections import defaultdict


def main():
    n = int(input())
    s = input()
    count = len(set(s))
    d = defaultdict(int)
    res = n
    i = 0
    d[s[0]] += 1
    j = 1
    while j < n:
        if len(d) == count:
            res = min(res, j - i)
            d[s[i]] -= 1
            if d[s[i]] == 0:
                del d[s[i]]
            i += 1
        else:
            d[s[j]] += 1
            j += 1
    while len(d) == count:
        res = min(res, j - i)
        d[s[i]] -= 1
        if d[s[i]] == 0:
            del d[s[i]]
        i += 1

    print(res)

main()


n = int(input())
flats = input()
types = set(flats)
counter = {}
menor = n
j = 0
for i in range(n):
    if counter.get(flats[i], 0) == 0:
        counter[flats[i]] = 1
    else:
        counter[flats[i]] += 1
    if len(counter) < len(types):
        continue
    while counter[flats[j]] > 1:
        counter[flats[j]] -= 1
        j += 1
    menor = min(menor, i-j+1)
    if menor == len(types):
        break
print(menor)


n = int(input())
flats = input()
types = set(flats)
counter = {}
menor = n
j = 0
for i in range(n):
    if flats[i] not in counter:
        counter[flats[i]] = 0
    counter[flats[i]] += 1
    if len(counter) < len(types):
        continue
    while counter[flats[j]] > 1:
        counter[flats[j]] -= 1
        j += 1
    menor = min(menor, i-j+1)
    if menor == len(types):
        break
print(menor)


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

p = set()
for c in s:
    p.add(c)

pc = len(p)

d = dict()
l = 0
r = 0
d[s[r]] = 1
while len(d) < pc:
    r += 1
    if s[r] in d:
        d[s[r]] += 1
    else:
        d[s[r]] = 1
m = r - l

while l + 1 < n:
    d[s[l]] -= 1
    if d[s[l]] == 0:
        del d[s[l]]
    l += 1
    while (r + 1 < n) and (len(d) < pc):
        r += 1
        if s[r] in d:
            d[s[r]] += 1
        else:
            d[s[r]] = 1
    if len(d) < pc:
        break
    m = min(m, r - l)
         
print(m + 1)



n = int(input())
s = input()
types = len(set(s))
d = dict()
c = 0
j = 0
ans = 10**10
for i in range(n):
    if s[i] not in d:
        d[s[i]] = 0
        c+=1
    d[s[i]]+=1
    if c ==types:
        while d[s[j]] > 1:
            d[s[j]]-=1
            j+=1
        ans = min(ans,i-j+1)
print(ans)


from sys import stdin
def main():
        n=int(stdin.readline())
        ville=stdin.readline()
        minimum=n
        maisons={}
        nbType=0
        for maison in ville:
                if maison!="\n" and maison not in maisons:
                        maisons[maison]=0
                        nbType+=1
        nbZeros=nbType-1
        inf=0
        sup=0
        maisons[ville[0]]+=1
        while n>sup:
                if nbZeros==0:
                        minimum=min(minimum,sup-inf+1)
                        maisons[ville[inf]]-=1
                        if maisons[ville[inf]]==0:
                                nbZeros+=1
                        inf+=1

                else:
                        sup+=1
                        if n>sup:
                                maisons[ville[sup]]+=1
                                if maisons[ville[sup]]==1:
                                        nbZeros-=1
        print(minimum)
main()


n=int(input())
s=input()
k=k1=n
q=set()
c=0
w=0
t=False
for i in range(n):
    if s[i] not in q:
        q.add(s[i])
        w=i
        k1=k=w-c+1
while True:
    if s[c] in s[c+1:w+1]:
        if w-c<k1:
            k1=w-c
            if k1<k:
                k=k1
        c+=1
    else:
        for i in range(c+1,n):
            if s[i]==s[c]:
                w=i
                t=True
                break
        if t==False:
            print(k)
            break
        t=False


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

q = len(set(s))

d = {}
count = 0

best = 999999999
j = 0
for i in range(n):
	if s[i] not in d:
		d[s[i]] = 0
		count += 1
	
	d[s[i]] += 1
	if count == q:
		while d[s[j]] > 1:
			d[s[j]] -= 1
			j += 1
		best = min(best, i - j + 1)

print(best)

def main():
    input()
    s = input()
    d = dict.fromkeys(s, 0)
    le, res = len(d), []
    iti, itj = (iter(enumerate(s)) for _ in "12")
    try:
        while True:
            while le:
                i, c = next(iti)
                if d[c]:
                    d[c] += 1
                else:
                    d[c] = 1
                    le -= 1
            while True:
                j, c = next(itj)
                if d[c] > 1:
                    d[c] -= 1
                else:
                    d[c], le = 0, 1
                    res.append(i - j)
                    break
    except StopIteration:
        print(min(res) + 1)


def __starting_point():
    main()

__starting_point()

n,s=int(input()),input()
dis = len(set(s))
mp = {}
l,r,m,cnt=0,0,99999999,0

for c in s:
    if c not in mp:
        mp[c]=0
        cnt+=1
    mp[c]+=1
    if cnt == dis:
        while mp[s[l]]>1:
            mp[s[l]]-=1
            l+=1
        m = min(m,r-l+1)
    r+=1
print(m)


n = int(input())
s = input()
all_types = set()
count = {}
for c in s:
    all_types.add(c)
    count[c] = 0
n_all_types = len(all_types)
def solve():
    ret = n
    first = 0
    last = 0
    n_types = 0
    while first <= last:
        while n_types < n_all_types:
            if last == n:
                return ret
            if count[s[last]] == 0:
                n_types += 1
            count[s[last]] += 1
            last += 1
        ret = min(ret, last - first)
        if count[s[first]] == 1:
            n_types -= 1
        count[s[first]] -= 1
        first += 1
    return ret
print(solve())


N = int(input())
A = list(map(ord, list(input())))
S = [0] * 150
for i in range(N):
	S[A[i]] += 1
Pokemon = len(S) - S.count(0)
L = 0
R = N
while(R - L > 1):
	M = (R + L) // 2
	l = 0
	r = 0
	S = [0] * 150
	count = 0
	is_ok = False
	while r < l + M:
		if S[A[r]] == 0:
			count += 1
		S[A[r]] += 1
		r += 1
	if count == Pokemon:
		is_ok = True
	while r < N and not is_ok:
		if S[A[l]] == 1:
			count -= 1
		S[A[l]] -= 1
		if S[A[r]] == 0:
			count += 1
		S[A[r]] += 1
		l += 1
		r += 1
		if count == Pokemon:
			is_ok = True
	if is_ok:
		R = M
	else:
		L = M
print(R)


from collections import Counter
c=Counter()
ans=n=int(input())
s=input()
k=len(set(s))
i=j=t=0
while j<n:
    while len(c)<k and j<n: c[s[j]]+=1; j+=1
    while len(c)==k:
        if j-i<ans: ans=j-i
        c[s[i]]-=1
        if c[s[i]]==0: del c[s[i]]
        i+=1
print(ans)


n=int(input())
stri=input()
dict={}
lenght=len(set(stri))
count=0
j=0
result=999999999
for i in range(n):
    if stri[i] not in dict:
        dict[stri[i]]=0
        count += 1

    dict[stri[i]]+=1
    if count==lenght:
        while dict[stri[j]]>1:
            dict[stri[j]]-=1
            j+=1
        result= min(result,i-j+1)
print(result)

n=int(input())
stri=input()
dict={}
lenght=len(set(stri))
count=0
j=0
result=999999999
for i in range(n):
    if stri[i] not in dict:
        dict[stri[i]]=0
        count += 1

    dict[stri[i]]+=1
    if count==lenght:
        while dict[stri[j]]>1:
            dict[stri[j]]-=1
            j+=1
        result= min(result,i-j+1)
print(result)