output_description: Print the number of triplets in question.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S
attempt: from bisect import bisect_left
  
  N = int(input())
  S = list(input())
  rix, gix, bix = [], [], []
  lrc = [{} for _ in range(N)]
  for i in range(N):
      c = S[i]
      lrc_d = lrc[i]
      if c == "R":
          rix.append(i)
          lrc_d["lg"] = 0
          lrc_d["rg"] = 0
          lrc_d["lb"] = 0
          lrc_d["rb"] = 0
      elif c == "G":
          gix.append(i)
          lrc_d["lr"] = 0
          lrc_d["rr"] = 0
          lrc_d["lb"] = 0
          lrc_d["rb"] = 0
      else:
          bix.append(i)
          lrc_d["lr"] = 0
          lrc_d["rr"] = 0
          lrc_d["lg"] = 0
          lrc_d["rg"] = 0
  rl = len(rix)
  gl = len(gix)
  bl = len(bix)
  # print(rix, gix, bix)
  for ri in rix:
      lg = bisect_left(gix, ri)
      lb = bisect_left(bix, ri)
      lrc_d = lrc[ri]
      lrc_d["lg"] = lg
      lrc_d["rg"] = gl - lg
      lrc_d["lb"] = lb
      lrc_d["rb"] = bl - lb
  for bi in bix:
      lr = bisect_left(rix, bi)
      lg = bisect_left(gix, bi)
      lrc_d = lrc[bi]
      lrc_d["lr"] = lr
      lrc_d["rr"] = rl - lr
      lrc_d["lg"] = lg
      lrc_d["rg"] = gl - lg
  for gi in gix:
      lr = bisect_left(rix, gi)
      lb = bisect_left(bix, gi)
      lrc_d = lrc[gi]
      lrc_d["lr"] = lr
      lrc_d["rr"] = rl - lr
      lrc_d["lb"] = lb
      lrc_d["rb"] = bl - lb
  # print(lrc)
  ans = 0
  mod = 10**9 + 7
  for i in range(N):
      if S[i] == "R":
          lg = lrc[i]["lg"]
          rg = lrc[i]["rg"]
          lb = lrc[i]["lb"]
          rb = lrc[i]["rb"]
          lgs = set([i - gix[_] for _ in range(lg)])
          rgs = set([gix[lg + _] - i for _ in range(rg)])
          lbs = set([i - bix[_] for _ in range(lb)])
          rbs = set([bix[lb + _] - i for _ in range(rb)])
          ans += (lg * rb) - len(lgs & rbs)
          ans += (rg * lb) - len(rgs & lbs)
          ans %= mod
      if S[i] == "G":
          lr = lrc[i]["lr"]
          rr = lrc[i]["rr"]
          lb = lrc[i]["lb"]
          rb = lrc[i]["rb"]
          lrs = set([i - rix[_] for _ in range(lr)])
          rrs = set([rix[lr + _] - i for _ in range(rr)])
          lbs = set([i - bix[_] for _ in range(lb)])
          rbs = set([bix[lb + _] - i for _ in range(rb)])
          ans += (lr * rb) - len(lrs & rbs)
          ans += (rr * lb) - len(rrs & lbs)
          ans %= mod
          # print(lr, rr, lb, rb)
          # print(lrs, rrs, lbs, rbs)
      if S[i] == "B":
          lg = lrc[i]["lg"]
          rg = lrc[i]["rg"]
          lr = lrc[i]["lr"]
          rr = lrc[i]["rr"]
          lgs = set([i - gix[_] for _ in range(lg)])
          rgs = set([gix[lg + _] - i for _ in range(rg)])
          lrs = set([i - rix[_] for _ in range(lr)])
          rrs = set([rix[lr + _] - i for _ in range(rr)])
          ans += (lg * rr) - len(lgs & rrs)
          ans += (rg * lr) - len(rgs & lrs)
          ans %= mod
      # print(i, ans, S[i], lrc[i])
  print(ans)
  
problem_description: Statement
  
  We have a string S of length N consisting of `R`, `G`, and `B`.
  
  Find the number of triples (i,~j,~k)~(1 \leq i < j < k \leq N) that satisfy
  both of the following conditions:
  
    * S_i \neq S_j, S_i \neq S_k, and S_j \neq S_k.
    * j - i \neq k - j.
samples: [{"input": "4\n    RRGB", "output": "1\n    \n\nOnly the triplet (1,~3,~4) satisfies both conditions. The triplet (2,~3,~4)\nsatisfies the first condition but not the second, so it does not count.\n\n* * *"}, {"input": "39\n    RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB", "output": "1800"}]