Problem:


Score : 700 points

Problem Statement

There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.

Snuke will perform the following operation zero or more times:

Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo 10^9+7.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1
:
C_N

Output

Print the number of possible final sequences of colors of the stones, modulo 10^9+7.

Sample Input 1

5
1
2
1
2
2

Sample Output 1

3

We can make three sequences of colors of stones, as follows:

(1,2,1,2,2), by doing nothing.

(1,1,1,2,2), by choosing the first and third stones to perform the operation.

(1,2,2,2,2), by choosing the second and fourth stones to perform the operation.

Sample Input 2

6
4
2
5
4
2
4

Sample Output 2

5

Sample Input 3

7
1
3
1
2
3
3
2

Sample Output 3

5



Sample input:
5
1
2
1
2
2


Sample output:
3

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

# memory = {}

# def dfs(stones, N, depth):
#     if N <= 2:
#         # print(" "*depth, stones, "leaf")
#         return 1
#     # print(" "*depth, stones)
#     if stones in memory:
#         return memory[stones]

#     # ans1 はじめの石使わない
#     # print(" "*depth, "ans1")
#     ans1 = dfs(stones[1:], N-1, depth+1)

#     # ans2 はじめの石を使う
#     try:
#         ind = stones[2:].index(stones[0])
#         # print(" "*depth, "ans2", c)
#         # print(" "*depth, ind, stones, stones[ind:])
#         ans2 = dfs(stones[2+ind:], N-ind-2, depth+1)
#     except:
#         ans2 = 0

#     ans = (ans1 + ans2) % MOD
#     memory[stones] = ans
#     return ans


def solve(N: int, C: "List[int]"):
    # print(dfs(tuple(C), N, 0))
    dp = [0]*N
    pre = 0
    souwa = [0]*N
    for i, s in enumerate(C):
        # print(dp, souwa, pre)
        if i == 0:
            dp[i] = 1
        else:
            if s == pre:
                dp[i] = dp[i-1]
            else:
                souwa[pre-1] = dp[i-1]
                dp[i] = dp[i-1] + souwa[s-1]
        pre = s
    # print(dp, souwa, pre)
    print(dp[N-1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, C)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
dic = {}
while i+1<len(C):
    dic[C[i]] = -1
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=1

DP = [1]
for i in range(len(C)):  
    if dic[C[i]]==-1:   
        DP.append(DP[-1])
    else:
        DP.append((DP[-1]+DP[dic[C[i]]])%(10**9+7))
    dic[C[i]] = i+1            
print(DP[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
p = 10**9+7
dp = [[1, 0] for _ in range(N)]
prev = [-1 for i in range(2*10**5)]
prev[C[0]] = 0
for i in range(1, N):
    if prev[C[i]] == -1:
        dp[i][0] = dp[i-1][0]
    elif prev[C[i]] == i-1:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1]
    else:
        idx = prev[C[i]]
        dp[i][1] = dp[idx][0] + max(dp[idx][1]-1, 0)
        dp[i][0] = (dp[i-1][0] + dp[i][1])%p
    prev[C[i]] = i
print(dp[-1][0])

Submission status: Runtime Error

Solution code:
pre = -1
N = int(input())
C = []
X = [[] for _ in range(2*10**5)]
i = 0
for _ in range(N):
    a = int(input())
    if a != pre:
        C.append(a)
        X[a].append(i)
        i += 1
    pre = a

N = len(C)
dp = [1] + [0] * N

for i in range(1, N+1):
    dp[i] = dp[i-1]
    for j in X[C[i-1]]:
        if j >= i - 1:
            break
        dp[i] += dp[j]
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
C = [int(sys.stdin.readline()) for _ in range(N)]
MOD = 10**9 + 7
A = []
for c in C:
    if A and A[-1] == c:
        continue
    A.append(c)
NA = len(A)
last = [-1] * NA
B = [-1] * NA
for i, a in enumerate(A):
    B[i] = last[a]
    last[a] = i

dp = [0] * NA
dp[0] = 1
for i in range(1, NA):
    prev = 0 if B[i] < 0 else dp[B[i]]
    dp[i] = (dp[i - 1] + prev) % MOD
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,*c=map(int,open(0).readlines())
l=[-1]*n
b=[]
for i in range(n):
  b.append(l[c[i]])
  l[c[i]]=i
dp=[1]+[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]
  if c[i]!=c[i-1]and b[i]>-1:
    dp[i]=(dp[i]+dp[b[i]])%(10**9+7)
print(dp[-2])

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
    tmp = int(input())
    C.append(tmp)
    
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
prev=-1
for i in range(N) :
  if i!=0:
    if map2[C[i]]!=-1 and prev!=C[i]:
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i
  prev=C[i]

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
  tmp = int(input())
  if tmp != prev:
    C.append(tmp)
  prev=tmp
mod = 10**9+7
map = [-1] * 2*10**5+1
l = [1] * len(C)
for i in range(len(C)) :
  if i!=0:
    if(map[C[i]]!=-1):
      l[i]=(l[map[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
  tmp = int(input())
  if tmp != prev:
    C.append(tmp)
  prev=tmp
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * len(C)
for i in range(len(C)) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
  tmp = int(input())
  if tmp != prev:
    C.append(tmp)
  prev=tmp
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * len(C)
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
  tmp = int(input())
  if tmp != prev:
    C.append(tmp)
  prev=tmp
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
C = [0]
for line in sys.stdin:
    c = int(line)
    if c[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
    tmp = int(input())
    if tmp != prev:
        C.append(tmp)
    prev = tmp
 
dp = [0]*(len(C)+1)
place = {}
dp[0] = 1
 
for i in range(len(C)):
    if place.get(C[i]) != None:
        dp[i+1] = dp[i] + dp[place.get(C[i])]
    else:
        dp[i+1] = dp[i]
    place[C[i]] = i+1
    
print(dp[-1]%(10**9+7))
# coding: utf-8
# Your code here!

N = int(input())
C = []

for _ in range(N):
    tmp = int(input())
    C.append(tmp)

dp = [0]*(len(C)+1)
place = {}
dp[0] = 1

for i in range(len(C)):
    if place.get(C[i]) != None:
        dp[i+1] = dp[i] + dp[place.get(C[i])]
    else:
        dp[i+1] = dp[i]
    place[C[i]] = i+1
    
print(dp[-1]%(10**9+7))
提出情報

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
 
prev = -1
 
for _ in range(N):
    tmp = int(input())
    C.append(tmp)
    
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for row in range(200000)]
b = 0
d = [0]
mod = 10 ** 9 + 7
mini_ans = 0
for i in range(n):
  c = int(input())
  if b != c:
    for j in a[c]:
      mini_ans += (d[j] + 1) % mod
    a[c].append(i)
  d.append(mini_ans % mod)
  b = c
print(d[-1]+1)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
 
N = I()
C = [I() for i in range(N)]
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for row in range(200000)]
b = 0
e = [int(input()) for i in range(n)]
d = [0]
mini_ans = 0
for i,c in enumerate(e):
  if b != c:
    for j in a[c]:
      mini_ans += d[j] + 1
    a[c].append(i)
  d.append(mini_ans)
  b = c
print(d[-1]+1)

Submission status: Runtime Error

Solution code:
N = input()
C = []
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for i in range(N) :
  if i!=0:
    if(map2[C[i]]!=-1):
      l[i]=(l[map2[C[i]]]+l[i-1])%mod
    else:
      l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
p=10**9 +7
n=int(input())
c=[int(i) for i in sys.stdin]
dic = dict()
for i in c:
    if i in dic:
        if dic[i]:
            dic[i] = False
    else:
        dic[i] = True
newline=[]
stack=0
for i in range(n):
  k=c.pop()
  if dic[k]:
    stack=k
    continue
  else:
    if stack!=k:
      newline.append(k)
    stack=k
result=sum([i-1 for i in Counter(newline).values()])%p
if result%2:
  print(pow(2,result//2 +1,p)-1)
else:
  print(pow(2,(result-1)//2,p)*3 -1)

Submission status: Runtime Error

Solution code:
mod=7+10**9
n=int(input())
c=[int(input()) for _ in [0]*n]
data=[0]*n+[1]
def dp(k,l):
    if data[k]>0:
        return data[k]
    if k>=n-1:
        return 1
    ans=0
    i=0
    while i<len(l):
        if l[i]==l[0]:
            j=i
            while j<len(l) and l[j]==l[0]:
                j+=1
            ans+=dp(j,l[j:])
            ans%=mod
            i=j
        i+=1
    data[k]=ans%mod
    return data[k]
print(dp(c))

Submission status: Runtime Error

Solution code:
mod=7+10**9
n=int(input())
c=[int(input()) for _ in [0]*n]
data=[0]*n
def dp(k,l):
    if data[k]>0:
        return data[k]
    if len(l)<=1:
        return 1
    ans=0
    i=0
    while i<len(l):
        if l[i]==l[0]:
            j=i
            while j<len(l) and l[j]==l[0]:
                j+=1
            ans+=dp(j,l[j:])
            ans%=mod
            i=j
        i+=1
    data[k]=ans%mod
    return data[k]
print(dp(c))

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
mod = 10**9+7
map2 = [-1] * 2*10**5
l = [1] * N
for(int i = 0; i < N; i++):
  if i!=0:
    l[i]=(l[map2[C[i]]]+l[i-1])%mod
  else:
    l[i]=l[i-1]
  map2[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N, C = map(int, input)
mod = 10**9+7
map = [-1] * 2*10**5
l = [1] * N
for(int i = 0; i < N; i++):
  if i!=0:
    l[i]=(l[map[C[i]]]+l[i-1])%mod
  else:
    l[i]=l[i-1]
  map[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
C = [input() for i in range(N)]

C2 = []
re = ""
L = {}
for i in C:
  if i != re:
    if i in L:
      L[i].append(len(C2))
    else:
      L[i] = []
    C2.append(i)
  re = i

LL = [-1] * len(C2)
for i in L:
  t = i
  for j in L[t]:
    LL[int(t)] = j
    t = j

DP = [-1] * (len(C2) + 1)

DP[-1] = 1
for i in range(len(C2) - 1, -1, -1):
  DP[i] = DP[i + 1]
  if LL[i] != -1:
    DP[i] += DP[LL[i]]

print(DP[0])

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
p=10**9 +7
n=int(input())
c=[int(i) for i in sys.stdin]
dic = dict()
for i in c:
    if i in dic:
        if dic[i]:
            dic[i] = False
    else:
        dic[i] = True
newline=[]
stack=0
for i in range(n):
  k=c.pop()
  if dic[k]:
    stack=k
    continue
  else:
    if stack!=k:
      newline.append(k)
    stack=k
result=sum([i-1 for i in Counter(newline).values()])%p
if result%2:
  print(pow(2,result//2 +1,p)-1)
else:
  print((pow(2,result-1//2 +1,p)-1)

Submission status: Runtime Error

Solution code:
N = int(input())
listC=list()
for n in range(N):
  listC.append(int(input()))

def reversi(li, ss, count):
  for n in range(ss, N-1):
    for i in range(n+1, N):
      if li[i] == li[n]:
        if i-n <= 1:
          break;
        else:
          newList = li
          count += 1
          count += reversi(li, n+1, 0)
          for s in range(n+1, i):
            newList[s] = li[i]
          count += reversi(newList, i, 0)
          break
  return count

print(reversi(listC, 0, 1))

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
c = [int(input()) for i in range(n)]
dp = [1 for i in range(n)]
dp2 = [-1 for i in range(n)]
memo = {}
ans = 0

def count(s):
  memo = {}
  res = 1
  for i in range(len(s)):
    if s[i] not in memo:
      memo[s[i]] = 1
    else:
      memo[s[i]] += 1
  for i in memo:
    res = res*((memo[i]*(memo[i]+1))//2)
  return res


dp2[c[0]] = 0
#print("dp",dp)
#print("dp2",dp2)
     
for i in range(1,n):
  
  if c[i] != c[i-1]:
    if dp2[c[i]] == -1:
      dp2[c[i]] = i
    else:
      dp[c[i]] = count(c[dp2[c[i]]:i])*dp[c[i]]
      ans += dp[c[i]]
      dp2[c[i]] = i

 # print(i,"dp",dp)
  #print(i,"dp2",dp2)
  #print(ans)   
#    for j in range(9):
#      ans += len()-1
#      bisect.bisect_left(li[i],)
print(ans)

Submission status: Runtime Error

Solution code:
N, C = map(int, input().split())
mod = 10**9+7
map = [-1] * 2*10**5
l = [1] * N
for(int i = 0; i < N; i++):
  if i!=0:
    l[i]=(l[map[C[i]]]+l[i-1])%mod
  else:
    l[i]=l[i-1]
  map[C[i]]=i

ans=l[N-1]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

a = {}
b = [[0 for i in range(0)] for j in range(N)]
pC = ''
pN = -1
for n in range(N):
    C = input()
    if C != pC:
        if pN >= 0:
            b[pN].append(n)
        if C in a:
            for v in a[C]:
                b[v].append(n)
            a[C].append(n)
        else:
            a[C] = [n]
        pN = n
    pC = C

def d(b, x, Y):
    if x == Y:
        return 1
    c = 0
    for g in b[x]:
        c += d(b, g, Y)
    return c

e = d(b, 0, N - 1)
print (e)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

N = int(input())
numberlist = [[] for i in range(200011)]
number = []
for i in range(N):
    a = int(input())
    if i > 0:
        if number[len(number)-1] == a:
            continue
        else:
            number.append(a)
            numberlist[a].append(i)
    else:
        number.append(a)
        numberlist[a].append(i)
periodlist = []
for i in range(N+1):
    for j in range(max(0, len(numberlist[i]) - 1)):
        if j == 0:
            periodlist.append([numberlist[i][j], numberlist[i][j+1]])
        else:
            periodlist.append([numberlist[i][j]+1, numberlist[i][j+1]])
periodlist.sort(key=itemgetter(1))
calculate = 0
dp = [0 for i in range(200011)]
dp[0] = 1
dp[-1] = 1
for i in range(len(periodlist)):
    for j in range(calculate, periodlist[i][1]):
        dp[j+1] = dp[j]
    dp[periodlist[i][1]] += dp[periodlist[i][0]-1]
    dp[periodlist][i][1] %= 1000000007
    calculate = periodlist[i][1]

print(dp[calculate]%1000000007)

Submission status: Runtime Error

Solution code:
def find_seq(stones, start, index, table):
    if start in table:
        return table[start]
    else:
        sequence = 1
        for i in range(start, len(stones)):
            stone = stones[i]
            if len(index[stone]) > 1:
                for j in index[stone]:
                    if j > i:
                        sequence += find_seq(stones, j+1, index, table)
        table[start] = sequence
        return sequence

N = int(input())
stones = []
index = {}
last = None
n_stone = 0
for i in range(N):
    stone = int(input())
    if stone != last:
        stones.append(stone)
        last = stone
        if stone in index:
            index[stone].append(n_stone)
        else:
            index[stone] = [n_stone]
        n_stone += 1
table = {}
sequence = find_seq(stones, 0, index, table)
#print(index, table)
print(sequence)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for row in range(200000)]
b = 0
e = [int(input()) for i in range(n)]
d = [0]
mini_ans = 0
for i,c in enumerate(e):
  if b != c:
    for j in a[c]:
      mini_ans += d[j] + 1
    a[c].append(i)
  d.append(mini_ans)
  b = c
print(d[-1]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
s = {}
pair = []
for i in range(n):
  ci = int(input())
  if ci in s:
    for j in range(len(c))[::-1]:
      if ci == c[j]:
        if j == len(c) - 1:
          break
        pair.append([j, len(c)])
  c.append(ci)
  s = set(c)
ans = 1
l = len(pair)
dp = [0] * l
dp[l-1] = 1
for i in range(l)[::-1]:
  end = pair[i][1]
  for j in range(i, l):
    if end < pair[j][0]:
      dp[i] = 1 + dp[j]
      break
  else:
    dp[i] = 1
print(sum(dp)+1)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
C = [0]
#c = [int(sys.stdin.readline()) for i in range(N)]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
#C = C+c
dp = [0] * (N + 2)
color = [[]for i in range((2*(10**4)+2))]
dp[0] = 1
dp[1] = 1
color[C[1]].append(1)
for i in range(2, N+1):
    dp[i] = dp[i - 1] + sum([dp[col - 1] for col in color[C[i]]])
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)
# print(dp)
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

def p2s(p):
  return ' '.join(p)
def s2p(s):
  return s.split(' ')
def compress(p):
  new_p = [p[0]]
  for i in range(1,len(p)):
    if new_p[-1] != p[i]:
      new_p.append(p[i])
  return new_p

_ = input()
_p = [c.strip() for c in sys.stdin]
# 連続する同じ色の石の塊は一つの石とみなせる
pattern = compress(_p)
N = len(pattern)

def onehop(p):
  result = set()
  # 始点
  for i in range(N-1):
    if p[i] == p[i+1]: continue # 同じ色が連続してるときは一番右端をとる
    # 終点
    for j in range(N-1, i+1, -1):
      if p[j] == p[j-1]: continue # 同じ色が連続してる時は一番左端をとる
      if p[i] == p[j]:
        # 間の石をひっくり返す
        new_p = [p[i] if i < k < j else p[k] for k in range(N)]
        result.add(p2s(new_p))
  return result


nows = {p2s(pattern),}
while True:
  nexts = set()
  for s in nows:
    if len(s) > 2:
      nexts |= onehop(s2p(s))
  allpattern |= nows
  if len(nexts) == 0:
    break
  nows = nexts

print(len(allpattern))

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = int(input())
C = []
last_idx = [0 for i in range(200000)]
bef = [0 for i in range(N+1)]
for i in range(1,N+1):
	c = int(input())
	C.append(c)
	bef[i] = last_idx[c]
	last_idx[c] = i
dp = [0 for i in range(N+1)]
dp[1] = 1
if N == 1 or N == 2:
	print(1)
	exit()

for i in range(2, N+1):
	if bef[i] < i-1:
		dp[i] = (dp[i-1] + dp[bef[i]]) % MOD
	else:
		dp[i] = dp[i-1]
print(dp[N])

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = int(input())
C = []
last_idx = [0 for i in range(N+1)]
bef = [0 for i in range(N+1)]
for i in range(1,N+1):
	c = int(input())
	C.append(c)
	bef[i] = last_idx[c]
	last_idx[c] = i
dp = [0 for i in range(N+1)]
dp[1] = 1
if N == 1 or N == 2:
	print(1)
	exit()

for i in range(2, N+1):
	if bef[i] < i-1:
		dp[i] = (dp[i-1] + dp[bef[i]]) % MOD
	else:
		dp[i] = dp[i-1]
print(dp[N])

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = int(input())
C = []
last_idx = [None for i in range(N+1)]
bef = [None for i in range(N+1)]
for i in range(1,N+1):
	c = int(input())
	C.append(c)
	if last_idx[c] != None:
		bef[i] = last_idx[c]
	last_idx[c] = i
dp = [0 for i in range(N+1)]
dp[1] = 1
for i in range(2, N+1):
	if bef[i] != None and bef[i] < i-1:
		dp[i] = (dp[i-1] + dp[bef[i]]) % MOD
	else:
		dp[i] = dp[i-1]
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
C = []
last_idx = [None for i in range(N+1)]
bef = [None for i in range(N+1)]
for i in range(1,N+1):
	c = int(input())
	C.append(c)
	if last_idx[c] != None:
		bef[i] = last_idx[c]
	last_idx[c] = i
dp = [0 for i in range(N+1)]
dp[1] = 1
for i in range(2, N+1):
	if bef[i] != None and bef[i] < i-1:
		dp[i] = dp[i-1] + dp[bef[i]]
	else:
		dp[i] = dp[i-1]
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys
sy=sys.stdin.readline

n=int(sy())
dp=[0]*(n+1)
lis=[0]*(2*10**5+1)
dp[0],dp[1],dp[2]=0,1,1
c1=int(sy())
c2=int(sy())
lis[c1]=1
lis[c2]=2
for i in range(3,n+1):
    c1=c2
    c2=int(sy())
    if c1==c2 or lis[c2]==0:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[lis[c2]]
    lis[c2]=i
    dp[i]%=1000000007
print(dp[n])

Submission status: Runtime Error

Solution code:
import sys
sy=sys.stdin.readline

n=int(sy())
dp=[0]*(n+1)
lis=[0]*(n+1)
dp[0],dp[1],dp[2]=0,1,1
c1=int(sy())
c2=int(sy())
lis[c1]=1
lis[c2]=2
for i in range(3,n+1):
    c1=c2
    c2=int(sy())
    if c1==c2 or lis[c2]==0:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[lis[c2]]
    lis[c2]=i
    dp[i]%=1000000007
print(dp[n])

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def comb2(N):
    return int(N*(N-1)/2)


N = int(input())
prev = -1
Col = []
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        prev = c
        Col.append(c)


cntF = [0]*(N+1)
forward = [0]*(len(Col)+1)
for i, c in enumerate(Col):
    forward[i] = cntF[c]
    cntF[c] += 1

cntB = [0]*(N+1)
back = [0]*(len(Col)+1)
for i in reversed(range(len(Col))):
    c = Col[i]
    back[i] = cntB[c]
    cntB[c] += 1

backr = back[::-1]
backr = list(accumulate(backr))
back = backr[::-1]
# print(forward)
# print(back)
ans = 1
for i in range(len(Col)):
    tmp = forward[i]*(back[i+1]+1)
   #print("tmp->", tmp)
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
j = 0
ans = 1
color = [-1 for i in range(n+1)]
for _ in range(n):
    i = int(input())
    if j == i:
        pass
    else:
        if color[i-1] == -1:
            color[i-1] = ans
        else:
            ans += color[i-1]
            if ans >= (10**9+7):
                ans = ans %(10**9+7)
            color[i-1] = ans
        j = i
if ans >= (10**9+7):
    ans = ans %(10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def comb2(N):
    return int(N*(N-1)/2)


N = int(input())
prev = -1
Col = []
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        prev = c
        Col.append(c)


cntF = [0]*(N+1)
forward = [0]*(len(Col)+1)
for i, c in enumerate(Col):
    forward[i] = cntF[c]
    cntF[c] += 1

cntB = [0]*(N+1)
back = [0]*(len(Col)+1)
for i in reversed(range(len(Col))):
    c = Col[i]
    back[i] = cntB[c]
    cntB[c] += 1

ans = 1+sum(forward)
for i in range(1, len(Col)-1):
    ans = ans + forward[i]*back[i+1]
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
[n] = [int(i) for i in input().split()]

char = {}
left = {}
right = {}
c_list = list()
prev = -1
j = 0

for i in range(0, n):
    c = int(input())

    if prev != c:
        prev = c
        c_list.append(c)
    else:
        continue

    if c not in char.keys():
        char[c] = 1
        left[c] = j
    else:
        char[c] = char[c] + 1
        right[c] = j
    j = j + 1

cnt = 0
for c in char.keys():
    cnt = cnt + (2 ** (char[c] - 1) - 1)
cnt = cnt + 1

idx_list = sorted(char.keys())
same = {}
for idx in idx_list:
    for ridx in range(idx + 1, max(idx_list) + 1):
        if right[idx] < left[ridx]:
            if idx not in same.keys():
                same[idx] = 1
            else:
                same[idx] = same[idx] + 1
            idx_list.remove(ridx)

for idx in sorted(same.keys()):
    cnt = cnt + (2 ** (same[idx] - 1))

print(cnt % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def comb2(N):
    return int(N*(N-1)/2)


N = int(input())
prev = -1
Col = []
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        prev = c
        Col.append(c)


cntF = [0]*(N+1)
forward = [0]*len(Col+1)
for i, c in enumerate(Col):
    forward[i] = cntF[c]
    cntF[c] += 1

cntB = [0]*(N+1)
back = [0]*(len(Col)+1)
for i in reversed(range(len(Col))):
    c = Col[i]
    back[i] = cntB[c]
    cntB[c] += 1

ans = 1+sum(forward)
for i in range(1, len(Col)-1):
    ans = ans + forward[i]*back[i+1]
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def comb2(N):
    return int(N*(N-1)/2)


N = int(input())
prev = -1
Col = []
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        prev = c
        Col.append(c)


cntF = [0]*(N+1)
forward = [0]*len(Col)
for i, c in enumerate(Col):
    forward[i] = cntF[c]
    cntF[c] += 1

cntB = [0]*(N+1)
back = [0]*(len(Col))
for i in reversed(range(len(Col))):
    c = Col[i]
    back[i] = cntB[c]
    cntB[c] += 1

ans = 1+sum(forward)
for i in range(1, len(Col)-1):
    ans = ans + forward[i]*back[i+1]
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
[n] = [int(i) for i in input().split()]

char = {}
left = {}
right = {}
c_list = list()
prev = -1
j = 0

for i in range(0, n):
    c = int(input())

    if prev != c:
        prev = c
        c_list.append(c)
    else:
        continue

    if c not in char.keys():
        char[c] = 1
        left[c] = j
    else:
        char[c] = char[c] + 1
        right[c] = j
    j = j + 1

cnt = 0
for c in char.keys():
    cnt = cnt + (2 ** (char[c] - 1) - 1)
cnt = cnt + 1

idx_list = sorted(char.keys())
same = {}
for idx in idx_list:
    for ridx in range(idx + 1, max(idx_list) + 1):
        if right[idx] < left[ridx]:
            if idx not in same.keys():
                same[idx] = 1
            else:
                same[idx] = same[idx] + 1
            idx_list.remove(ridx)

for idx in sorted(same.keys()):
    cnt = cnt + (2 ** (same[idx] - 1))
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
c=[int(input()) for _ in range(n)]
x=[c[0]]
for i in range(1,n):
    if c[i]!=c[i-1]:
        x.append(c[i])
#print(x)

dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
res2=[0 for _ in range(max(x)+1)]
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:#左端スタートで１つ目の場合
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])+res2[res[x[i]][-1]-1]
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
    res2[x[i-1]]+=dp[i-1]
    #print(dp,res2)
print((dp[len(x)-1]+1)%(10**9+7))
#print(res)

Submission status: Runtime Error

Solution code:
import sys
sy=sys.stdin.readline

n=int(sy())
dp=[0]*(n+1)
lis=[0]*(n+1)
dp[0],dp[1],dp[2]=0,1,1
c1=int(sy())
c2=int(sy())
lis[c1]=1
lis[c2]=2
for i in range(3,n+1):
    c1=c2
    c2=int(sy())
    if c1==c2 or lis[c2]==0:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[lis[c2]]
    lis[c2]=i
print(dp[n])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
typedef long long ll;

int main(){
    ll r = 0,mod = 1e9+7;
    int N,c;
    cin >> N;
    vector<int> v(N+1,0);
    vector<ll> ac(N+1,1);
    map <int,vector<int>> mp;
    
    for (int i=1;i<=N;++i){
        cin >> c;
        v[i] = c;
        mp[c].push_back(i);
        if (mp[c].size()>=2 && mp[c][mp[c].size()-2]<i-1){
            int tmp = mp[c].size()-2;
            tmp = mp[c][tmp];
            r = ac[tmp]+ac[i-1];
        }
        else {
            r = ac[i-1];
        }
        r%=mod;
        ac[i] = r; 
    }
    cout << ac[N]%mod << endl;
}

Submission status: Runtime Error

Solution code:
N = int(input())
C = [0 for i in range(N)]
alpha = {}
for i in range(N):
    C[i] = int(input())
    if C[i] in alpha.keys():
        alpha[C[i]].append(i)
    else:
        alpha[C[i]] = [i]
sosu = 10 ** 9 + 7

dp = [1 for i in range(N)]
mae = C[1]
for i in range(2,N):
    dp[i] = dp[i-1]
    if C[i] != mae:
        numlist = alpha[C[i]]
        for j in numlist:
            if j < i and j>=1:
                dp[i] += dp[j-1]
            elif j == 0:
                dp[i] += 1
            else:
                break
    mae = C[i]
    dp[i] = dp[i] % sosu
print(dp[N-1])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
typedef long long ll;

int main(){
    ll r = 0,mod = 1e9+7;
    int N,c;
    cin >> N;
    vector<int> v(N+1,0);
    vector<ll> ac(N+1,1);
    map <int,vector<int>> mp;
    
    for (int i=1;i<=N;++i){
        cin >> c;
        v[i] = c;
        mp[c].push_back(i);
        if (mp[c].size()>=2 && mp[c][mp[c].size()-2]<i-1){
            int tmp = mp[c].size()-2;
            tmp = mp[c][tmp];
            r = ac[tmp]+ac[i-1];
        }
        else {
            r = ac[i-1];
        }
        r%=mod;
        ac[i] = r; 
    }
    for (int i=1;i<=N;++i){
        cout << ac[N]%mod << ' ';
    }
}

Submission status: Runtime Error

Solution code:
 = [0 for i in range(N)]
alpha = {}
for i in range(N):
    C[i] = int(input())
    if C[i] in alpha.keys():
        alpha[C[i]].append(i)
    else:
        alpha[C[i]] = [i]
sosu = 10 ** 9 + 7

dp = [1 for i in range(N)]
mae = C[1]
for i in range(2,N):
    dp[i] = dp[i-1]
    if C[i] != mae:
        numlist = alpha[C[i]]
        for j in numlist:
            if j < i and j>=1:
                dp[i] += dp[j-1]
            elif j == 0:
                dp[i] += 1
            else:
                break
    mae = C[i]
    dp[i] = dp[i] % sosu
print(dp[N-1])

Submission status: Runtime Error

Solution code:
import sys
sy=sys.stdin.readline

n=int(sy())
dp=[[] for _ in range(n+1)]
lis=[[] for _ in range(n+1)]
dp[0],dp[1],dp[2]=0,1,1
c1=int(sy())
c2=int(sy())
lis[c1]+=[1]
lis[c2]+=[2]
for i in range(3,n+1):
    c1=c2
    c2=int(sy())
    if c1==c2 or lis[c2]==[]:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[lis[c2][-1]]
    lis[c2]+=[i]
print(dp[n])