Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0 and i < n:
                tmp += DP[i+1][j-1][k]*j
            if k > 0 and j < n:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
n,k = map(int,input().split())
p = 1000000007

xCy = {}
def cmb(x, y):
    if x < 0 or y < 0: return 0
    if y == 0 or y == x: return 1
    if y == 1: return x
    if (x,y) in xCy: return xCy[(x,y)]
    xCy[(x,y)] = (cmb(x-1,y) + cmb(x-1,y-1))%p
    return xCy[(x,y)]

for i in range(1,k+1):
  print((cmb(k-1,i-1)*cmb(n-k+1,n-k-i+1))%p)

### FIXED CODE ###

from operator import mul
from functools import reduce
n,k = map(int,input().split())
p = 1000000007


def cmb(x,y):
    if x < 0 or y < 0: return 0
    y = min(x-y,y)
    if y == 0: return 1
    over = reduce(mul, range(x, x - y, -1))
    under = reduce(mul, range(1,y + 1))
    return (over // under)%p


for i in range(1,k+1):
  print((cmb(k-1,i-1)*cmb(n-k+1,n-k-i+1))%p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    ans = 0
    d = {}
    T = [0]*(n+1)
    for i in range(n):
        T[i+1] = int(s[n-1-i])*10**i+T[i]
        t = T[i+1]%mod
        if t in d:
            d[t] += 1
        else:
            d[t] = 1
    for k in d:
        if k != 0:
            ans += d[k]*(d[k]-1)//2
        else:
            ans += d[k]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,q = map(int, input().split())
s = list(input())
lr_list = [list(map(int,input().split())) for _ in range(q)]

for l,r in lr_list:
    count = 0
    tmp_list = []
    for i in range(len(s[l-1:r])):
        if i+1 == len(s[l-1:r]):
            break
        tmp_list.append(s[l-1:r][i]+s[l-1:r][i+1])
    for p in tmp_list:
        if 'AC' == p:
            count += 1
    print(count)

### FIXED CODE ###

n,q = map(int, input().split())
s = list(input())
lr_list = [list(map(int,input().split())) for _ in range(q)]
tmp_list = [0]*(n+1)

for i in range(1,n):
    if s[i-1]=='A' and s[i]=='C':
        tmp_list[i] = tmp_list[i-1]+1
    else:
        tmp_list[i] = tmp_list[i-1]

for l,r in lr_list:
    print(tmp_list[r-1]-tmp_list[l-1])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
S.append(0)
tmp_input = []
count = 0
Ans = []

for i in range(Q):
    x,y = map(int,input().split())
    count = 0
    tmp_List = S[x-1:y]
    tmp_List.append(0)
    for j in range(len(tmp_List)-1):
        if (tmp_List[j] == 'A') & (tmp_List[j+1] == 'C') ==True:
            count += 1
    Ans.append(count)
for i in range(len(Ans)):
    print(Ans[i])




### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())
S.append(0)
par = [0]*(N+1)#par[0]は無視
Ans = []
for i in range(N):
        par [i+1]=par[i]+(1 if (S[i]=='A') & (S[i+1]=='C') else 0)
for i in range(Q):
        x,y = map(int,input().split())
        print(par[y-1]-par[x-1])
### BUGGY CODE ###

# 初期入力
N= int(input())
S =input()

from collections import Counter
c = Counter(S)
count_all =c["R"] * c["G"] * c["B"]
count =0
for i,v in enumerate(S):
    for j in range(1,(N+1)//2):
        if 0 <= i-j and i+j <N: 
            if S[i-j]=="R" and S[i] =="G" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            if S[i-j]=="R" and S[i] =="B" and S[i+j] =="G":
                #print(i-j,i,i+j)
                count +=1
            if S[i-j]=="G" and S[i] =="R" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            if S[i-j]=="G" and S[i] =="B" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            if S[i-j]=="B" and S[i] =="G" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            if S[i-j]=="B" and S[i] =="R" and S[i+j] =="G":
                count +=1
                #print(i-j,i,i+j)

print(count_all - count)  

### FIXED CODE ###

# 初期入力
N= int(input())
S =input()


#
R_index=[]
G_index=[]
B_index=[]
for i,v in enumerate(S):
    if v =="R":
        R_index.append(i)
    if v =="G":
        G_index.append(i)
    if v =="B":
        B_index.append(i)

# 例　R_index各要素から等距離離れたところに左にG、右にBがあればOK
R_B =[]
B_G =[]
count_ij_jk_onaji =0
for r in R_index:
    for g in G_index:
        if 0<=g-(r-g) and g-(r-g)<N  :
            #if S[g-(r-g)]=="B" and r<g:
            if S[g-(r-g)]=="B" :
                count_ij_jk_onaji +=1
               # print(r,g,g-(r-g),"B")
for b in B_index:
    for r in R_index:
        if 0<=r-(b-r) and r-(b-r)<N :
            #if S[r-(b-r)] == "G" and b<r:
            if S[r-(b-r)] == "G" :
                count_ij_jk_onaji +=1
                #print(r,b,r-(b-r),"G")
for g in G_index:
    for b in B_index:
        if 0<=b-(g-b) and b-(g-b)<N :
            #if S[b-(g-b)] =="R" and g<b:
            if S[b-(g-b)] =="R":
                count_ij_jk_onaji +=1
                #print(b,g,b-(g-b),"R")

            
#3つとも異なる文字=all
kotae_all = len(R_index) * len(G_index) * len(B_index) 
print(kotae_all -count_ij_jk_onaji)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    for i in range(N):
        temp = int(S[N - i - 1:]) % P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = 0
    power = 1
    for i in range(N):
        power *= 10
        power %= P
        temp += power * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)
### BUGGY CODE ###

n = int(input())
l = list(input())
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    if l[i] != l[j]:
      for k in range(j+1,n):
        if l[j] != l[k] and l[i] != l[k] and j-i != k-j:
          count += 1
print(count)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
s = list(input())

c  = Counter(s)  

num = c['R']*c['G']*c['B']

for j in range(n):
    for d in range(1,min(j,n-j-1)+1):
        i = j-d
        k = j+d
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            num -= 1
print(num)
### BUGGY CODE ###

import copy

N, K = map(int, input().split())
A = list(map(int, input().split()))

## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A = sorted(A)
A_Left = copy.copy(A)
duplicatedList = []
while len(A_Left) > 0:
    if A_Left[0] in A_Left:
        kinds += 1
        duplicatedList.append(A.count(A_Left[0]))
        for j in range(A_Left.count(A_Left[0])):
            A_Left.remove(A_Left[0])

if kinds <= K:
    print('0')
elif kinds > K:
    duplicatedList = sorted(duplicatedList)
    i = 0
    tmp = 0
    while kinds > K:
        kinds -= 1
        while duplicatedList[i] > 0:
            tmp += 1
            duplicatedList[i] -= 1
        i += 1
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B=[]
C=[]
for i in range(N):
    B.append(A[i]-1)
for i in range(N):
    C.append(A[i]+1)
D=[]
D=A+B+C
mx=0
for i in D:
    cnt=0
    for j in range(N):
        if i==A[j]:
            cnt+=1
        elif i==B[j]:
            cnt+=1
        elif i==C[j]:
            cnt+=1
    mx=max(mx,cnt)
print(mx)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B=[]
C=[]
for i in range(N):
    B.append(A[i]-1)
for i in range(N):
    C.append(A[i]+1)
D=[]
D=A+B+C
mx=0
E=[0]*10**6
for i in D:
    E[i]+=1
    
print(max(E))
### BUGGY CODE ###

s=input()
for i in range(int(input())):
    a=input()
    if a[0]=="1":
        s=s[::-1]
    elif a[0]=="2":
        if a[2]=="1":
            s=s[::-1]
            s=s+a[4]
            s=s[::-1]
        else:
            s=s+a[4]
print(s)          
            
        

### FIXED CODE ###

from collections import deque
 
S = deque(list(input()))
Q = int(input())
rvs = False
 
for q in range(Q):
    query = list(input().split())
    if len(query) > 1:
        if query[1] == "1":
            if rvs:
                S.append(query[2])
            else:
                S.appendleft(query[2])
        elif query[1] == "2":
            if rvs:
                S.appendleft(query[2])
            else:
                S.append(query[2])
    else:
        rvs = not (rvs)
 
if rvs:
    S.reverse()
 
print("".join(S))
### BUGGY CODE ###

N = int(input())
list_A = list(map(int,input().split()))

for i in range(N):
    count = 0
    count = list_A.count(i+1)
    print(count)

### FIXED CODE ###

N = int(input())
list_A = list(map(int,input().split()))
B = [0]*N

for a in list_A:
    B[a-1] += 1

for i in range(N):
    print(B[i])
### BUGGY CODE ###


S = input()

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * 10 ** i) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr[1:]:
    ans += v * (v - 1) // 2
print(ans)


### FIXED CODE ###


S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

s = input()
t = input()
N = len(s)

if t in s:
    print(s.find(t) + len(t))
else:
    schr = dict()
    for i in range(N):
        if s[i] in schr:
            schr[s[i]].append(i+1) 
        else:
            schr[s[i]] = [i+1]

    schrset = set(schr)
    ans, pos, pre, back = 0, 0, "#", False
    for i in range(len(t)):
        if t[i] in schrset:
            c = schr[t[i]]
            if c[-1] <= pos:
                ans += N - pos + c[0]
                pos, back = c[0], True
            else:
                if pre != t[i] or back:
                    j = 0
                while c[j] <= pos:
                    j += 1
                ans += c[j] - pos
                pos, pre, back = c[j], t[i], False
        else:
            print(-1)
            exit()
    print(ans)

### FIXED CODE ###

s = input()
t = input()
N, M = len(s), len(t)

schr, indchr = dict(), dict()
for i in range(N):
    if s[i] in schr:
        schr[s[i]].append(i+1) 
    else:
        schr[s[i]] = [i+1]
        indchr[s[i]] = 0

schrset = set(schr)
ans, pos, pre, back = 0, 0, set(), True
for i in range(M):
    if t[i] in schrset:
        c = schr[t[i]]
        if c[-1] <= pos:
            ans += N - pos + c[0]
            pos = c[0]
            if not back:
                for x in indchr.keys():
                    indchr[x] = 0
                back, pre = True, set()
        else:
            j = indchr[t[i]]
            while c[j] <= pos:
                j += 1
            if j > 0:
                pre.add(t[i])
            ans += c[j] - pos
            pos, back, indchr[t[i]] = c[j], False, j
    else:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))

s = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i] < l[j] + l[k] and l[j] < l[k] + l[i] and l[k] < l[i] + l[j]:
                s += 1

print(s)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))

s = 0

l.sort()

for i in range(n-2):
    j = n-2
    k = n-1
    while i < j:
        if l[k] >= l[i] + l[j] and j < k:
            #print(0, i, j, k)
            k -= 1
        else:
            #print(1, i, j, k)
            s += k - j
            j -= 1


print(s)
### BUGGY CODE ###

A, B, N = map(int, input().split())

tmp = 0
a = 0
i = 0
for i in range(B - 1, N + 1, B):
    if (s := (A * i) // B - A * (a)) > 0:
        tmp = max(s, tmp)
    else:
        break

if i >= N - B:
    for i in range(N, N - N % B - 1, -1):
        if (s := (A * i) // B - A * (i // B)) > 0:
            tmp = max(s, tmp)
        else:
            break

print(tmp)



### FIXED CODE ###

global A, B
A, B, N = map(int, input().split())

def f(num):
    return(A * num) // B - A * (num // B)

print(f(min(B - 1, N)))
### BUGGY CODE ###

n = int(input())

adj = [[False for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

weights = [9900000] * n


def search(goal, path, weight):
    e = path[-1]
    if weight < weights[goal]:
        if e == goal:
            weights[goal] = weight
        else:
            for v, c in enumerate(adj[e]):
                if (v not in path) and (c is not False):
                    path.append(v)
                    weight += c
                    search(goal, path, weight)
                    weight -= c
                    path.pop()


for i in range(n):
    search(i, [0], 0)

for v, w in enumerate(weights):
    print(v, w)

### FIXED CODE ###

n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = [v for v in range(n)]

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.remove(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)
### BUGGY CODE ###

from itertools import groupby

input()
a = []
r = 0
for k, g in groupby(sorted(map(int, input().split()))):
  for x in a:
    if k % x == 0:
      break
  else:
    a.append(k)
    if len(list(g)) == 1:
      r += 1
print(r)


### FIXED CODE ###

N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
A.sort()
 
cnt = 0
A_set = set(A)
for i in A_set:
    diff = A.count(i) - i
    if diff >= 0:
        cnt += diff
    else:
        cnt += A.count(i)
print(cnt)

### FIXED CODE ###

import collections
N = int(input())
A = [int(x) for x in input().split()]
c = collections.Counter(A)

tmp = 0
for k, v in c.items():
    if v < k:
        tmp += v
    else:
        tmp += (v - k)
print(tmp)
### BUGGY CODE ###

a,b=map(int,input().split())
e=[]
for i in range(a):
    c,d=map(int, input().split())
    e+=[c]*d
e.sort()
print(sum(e[:b]))

### FIXED CODE ###

a,b=map(int,input().split())
e=[]
for i in range(a):
    c,d=map(int, input().split())
    e+=[[c,d]]
e.sort()
a=i=j=0
while i < b:
    a+=(e[j][0]*e[j][1])
    i+=e[j][1]
    j+=1
print(a-((i-b)*e[j-1][0]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    ans = 0
    for r_i in r_arr:
        for g_i in g_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2
            central = (max_i + min_i) / 2

            tgt_b_arr = b_arr[::]

            if minmin in tgt_b_arr:
                tgt_b_arr.remove(minmin)
            if maxmax in tgt_b_arr:
                tgt_b_arr.remove(maxmax)
            if exists_central == 0:
                if central in tgt_b_arr:
                    tgt_b_arr.remove(central)
            ans += len(tgt_b_arr)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    max_dict = dict()
    for elem in max_arr:
        max_dict[elem] = 1

    except_num = 0
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2

            if minmin in max_dict:
                except_num += 1
            if maxmax in max_dict:
                except_num += 1
            if exists_central == 0:
                central = (max_i + min_i) / 2
                if central in max_dict:
                    except_num += 1

    ans = len(r_arr) * len(g_arr) * len(b_arr) - except_num
    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing
### BUGGY CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])