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:
from collections import defaultdict
from bisect import *
def solve():
  	mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]-1])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_left(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
            dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    ends = [-1]
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
                ends.append(l[i+1])
    selist = [[-1,-1]]+sorted(selist,key=lambda x:x[1])
    # s_ind = {}
    # for i,(s,e) in enumerate(selist):
        # e_ind[e] = i
    # ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist))
    for i in range(1,len(selist)):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,selist[i][0])
        dp[i] += dp[ind-1]
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
MOD = 10**9+7

n, *C = map(int, read().split())
dp = [0]*(n+1)
dp[0] = 1
idx = [-1]*(10**5+1)
for i, c in enumerate(C, 1):
  dp[i] = dp[i-1]
  if idx[c] != -1 and idx[c] < i-1:
    dp[i] += dp[idx[c]]
    dp[i] %= MOD
  idx[c] = i
print(dp[-1])

Submission status: Runtime Error

Solution code:
N=int(input())
pr=10**9+7
a=0
l=[0]*N
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(N+1)
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*N
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
mod=10**9+7
B=[A[0]-1]
for i in range(1,N):
  if A[i]!=A[i-1]:
    B.append(A[i]-1)
n=len(B)
used=[-1]*N
used[B[0]]=0
dp=[0]*n
dp[0]=1
for i in range(1,n):
  if used[B[i]]==-1:
    dp[i]=dp[i-1]
  else:
    a=used[B[i]]
    dp[i]=(dp[i-1]+dp[a])%mod
  used[B[i]]=i
print(dp[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def IR_(n): return [II() - 1 for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

# 解説AC
# ナニコレこんなの解けるの？ｗ
# 数え上げはだいたいDP
# ICPCのも水パフォに見えてきた
# このようなDPの問題をもっと解きたい

#solve
def solve():
    n = II()
    c = [n] + IR_(n) + [n]
    dp0 = [0] * (n + 1)
    dp1 = [0] * (n + 1)
    dp1[c[0]] = 1
    for i in range(n + 1):
        if c[i] != c[i + 1]:
            dp0[i] += dp1[c[i]]
            dp0[i] %= mod
            dp1[c[i + 1]] += dp0[i]
            dp1[c[i + 1]] %= mod
        else:
            dp0[i] = dp0[i - 1]
    print(dp0[-1])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
l = [int(input()) for _ in range(N)]
dp = [0] * (N+1)
pos = [-1]*(N+1)
dp[0] = 1
MOD = 10**9+7

for i in  range(1, N+1):
    p = pos[l[i-1]]
    if i-p>1 and p!=-1:
        dp[i] += dp[p]
    pos[l[i-1]] = i
    dp[i] += dp[i-1]
    dp[i] %= MOD
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n; cin >> n;

    vector<int64_t> ns(n);
    for (auto& v: ns) cin >> v;
    
    vector<set<int>> gs(200001);
    for(int i = 0; i < n; i++) {
        gs[ns[i]].insert(i);
    }

    vector<int64_t> dp(n);
    dp[n - 1] = 1;
    for (int i = n - 2; 0 <= i; i--) {
        int64_t v = ns[i];
        auto it = gs[v].find(i);
        assert(it != gs[v].end());
        it++;
        if (it == gs[v].end()) {
            dp[i] = dp[i+1];
        }
        else if (*it == i + 1) {
            dp[i] = dp[i+1];
        }
        else {
            dp[i] = dp[i+1] + dp[*it];
            dp[i] %= 1000000007;
        }
    }

    cout << dp[0] << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(int)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i] + table[x]
  
  dp[N-1-i]%=mod
  table[x]+=d[N-1-i]

print(dp[0])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1)
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
  dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Runtime Error

Solution code:
#reversi
n=int(input())
lists=[]
for i in range(n):
    a=int(input())
    lists.append(a)
dp=[0 for i in range(n+1)]
dp[0]=1

before=[0 for i in range(n+1)]

for i in range(n):
    a=lists[i]
    if before[a]==0:
        dp[i+1]=dp[i]
        before[a]=i+1
    elif before[a]!=0:
        if before[a]==i:
            before[a]=i+1
            dp[i+1]=dp[i]
        else:
            dp[i+1]=dp[i]+dp[before[a]]
            before[a]=i+1
print(dp[n])

Submission status: Runtime Error

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

N = int(input())
C = [int(input()) for _ in range(N)]
C = C[::-1]
mod = 10 ** 9 + 7

newC = []
while C:
    c = C.pop()
    if not newC or newC[-1] != c:
        newC.append(c)
N = len(newC)

seen = [0] * (10 ** 5 + 10)
dp = [0] * (N + 1)
dp[0] = 1
seen[newC[0]] = 1

for i, c in enumerate(newC[1:], start=1):
    cnt = seen[c]
    seen[c] = (seen[c] + dp[i - 1]) % mod
    dp[i] = (dp[i - 1] + cnt) % mod

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

Submission status: Runtime Error

Solution code:
from  bisect import *
mod=10**9+7
N=int(input())
c=[int(input()) for i in range(N)]
place=[[] for i in range(N+100)]
for i in range(N):
    place[c[i]].append(i)
dp=[0 for i in range(N+100)]
dp[0]=1
for i in range(1,N+1):
    dp[i]+=dp[i-1]
    color = c[i-1]
    it = bisect_left(place[color],i-1)
    if it>0:
        j=place[color][it -1]
        if (i-1) -j>1:
            dp[i]+=dp[j+1]
    dp[i]%=mod

print(dp[N]%mod)

Submission status: Runtime Error

Solution code:
from  bisect import *
mod=10**9+7
N=int(input())
c=[int(input()) for i in range(N+100)]
place=[[] for i in range(N+100)]
for i in range(N):
    place[c[i]].append(i)
dp=[0 for i in range(N+100)]
dp[0]=1
for i in range(1,N+1):
    dp[i]+=dp[i-1]%mod
    color = c[i-1]
    it = bisect_left(place[color],i-1)
    if it>0:
        j=place[color][it -1]
        if i-1 -j>1:dp[i]+=dp[j+1]

print(dp[N]%mod)

Submission status: Runtime Error

Solution code:
from  bisect import *
mod=10**9+7
N=int(input())
c=[int(input()) for i in range(N)]
place=[[] for i in range(N+1)]
for i in range(N):
    place[c[i]].append(i)
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
    dp[i]+=dp[i-1]%mod
    color = c[i-1]
    it = bisect_left(place[color],i-1)
    if it>0:
        j=place[color][it -1]
        if i-1 -j>1:dp[i]+=dp[j+1]

print(dp[N]%mod)

Submission status: Runtime Error

Solution code:
from  bisect import *
mod=10**9*7
N=int(input())
c=[int(input()) for i in range(N)]
place=[[] for i in range(N+1)]
for i in range(N):
    place[c[i]].append(i)
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
    dp[i]+=dp[i-1]
    color = c[i-1]
    it = bisect_left(place[color],i-1)
    if it>0:
        j=place[color][it -1]
        if i-1 -j>1:dp[i]+=dp[j+1]

print(dp[N]%mod)

Submission status: Runtime Error

Solution code:
from  bisect import *
N=int(input())
c=[int(input()) for i in range(N)]
place=[[] for i in range(N+1)]
for i in range(N):
    place[c[i]].append(i)
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
    dp[i]+=dp[i-1]
    color = c[i-1]
    it = bisect_left(place[color],i-1)
    if it>0:
        j=place[color][it -1]
        if i-1 -j>1:dp[i]+=dp[j+1]

print(dp[N])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
#途中

N=int(input())

C=[0]*2*10**5

ans=1
pre=-1

#ansの数にも影響を受ける
for _ in range(N):
    c=int(input())
    if pre!=c:
        ans+=C[c]
        C[c]+=1*ans
    pre=c
    print(ans,C[:10])
#print(ans)

Submission status: Runtime Error

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

N = int(input())
C = [int(input()) for _ in range(N)]+[-1]
l = []

for i in range(N):
    if C[i]!=C[i+1]:
        l.append(C[i])

dp = [0]*(len(l))
acc = [0]*(2*10**5+100)
dp[0] = 1
acc[l[0]] = 1
acc[l[1]] = 1
MOD = 10**9+7

for i in range(1, len(l)):
    dp[i] = acc[l[i]]
    
    if i<len(l)-1:
        acc[l[i+1]] += dp[i]
        acc[l[i+1]] %= MOD

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

dp = [0] * N
prev_i = [-1] * (10**5 + 1)

dp[0] = 1
prev_i[A[0]] = 0

for i in range(1, N):
  a = A[i]
  if prev_i[a] >= 0:
    if prev_i[a] == i - 1:
      dp[i] = dp[i - 1]
    else:
      dp[i] = dp[i - 1] + dp[prev_i[a]]
  else:
    dp[i] = dp[i - 1]
  prev_i[a] = i
  #print(i, dp, prev_i)

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

dp = [0] * N
prev_i = [-1] * (10**5 + 1)

dp[0] = 1
prev_i[A[0]] = 0

for i in range(1, N):
  a = A[i]
  if prev_i[a] != -1:
    if prev_i[a] != i - 1:
      dp[i] = dp[i - 1] + dp[prev_i[a]]
    else:
      dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1]
  prev_i[a] = i
  #print(i, dp, prev_i)

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

dp = [0] * N
prev_i = [-1] * (N + 1)

dp[0] = 1
prev_i[A[0]] = 0

for i in range(1, N):
  a = A[i]
  if prev_i[a] != -1:
    if prev_i[a] != i - 1:
      dp[i] = dp[i - 1] + dp[prev_i[a]]
    else:
      dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1]
  prev_i[a] = i
  #print(i, dp, prev_i)

print(dp[-1])

Submission status: Runtime Error

Solution code:
import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
app = [0 for i in range(n+1)]
mod = 10**9+7
pair = []
for i in range(n):
  x = a[i]
  if app[x] != 0 and i != app[x]:
    pair.append([app[x],i+1])
  app[x] = i+1
pair.sort()
ps = len(pair)
ans = 1
cntls = []
order = []
sumtot = []
for i in range(ps-1,-1,-1):
  [s,t] = pair[i]
  if i == ps-1:
    cntls.append([-s,1])
    order.append(-s)
    sumtot.append([-s,1])
  elif t>-cntls[0][0]:
    cntls.append([-s,1])
    order.append(-s)
    sumtot.append([-s,sumtot[-1][1]+1])
  else:
    x = bisect.bisect_right(order,-t)
    cntls.append([-s,sumtot[x-1][1]+1])
    order.append(-s)
    sumtot.append([-s,(sumtot[-1][1]+sumtot[x-1][1]+1)%mod])
if pair == []:
  print(1)
else:
  print((sumtot[-1][1]+1)%mod)

Submission status: Runtime Error

Solution code:
import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
app = [0 for i in range(n+1)]
mod = 10**9+7
pair = []
for i in range(n):
  x = a[i]
  if app[x] != 0 and i != app[x]:
    pair.append([app[x],i+1])
  app[x] = i+1
pair.sort()
ps = len(pair)
ans = 1
cntls = []
order = []
sumtot = []
for i in range(ps-1,-1,-1):
  [s,t] = pair[i]
  if i == ps-1:
    cntls.append([-s,1])
    order.append(-s)
    sumtot.append([-s,1])
  elif t>-cntls[0][0]:
    cntls.append([-s,1])
    order.append(-s)
    sumtot.append([-s,sumtot[-1][1]+1])
  else:
    x = bisect.bisect_right(order,-t)
    cntls.append([-s,sumtot[x-1][1]+1])
    order.append(-s)
    sumtot.append([-s,(sumtot[-1][1]+sumtot[x-1][1]+1)%mod])
print((sumtot[-1][1]+1)%mod)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(N + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table)
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  if j < len(table[a[i]]):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])

Submission status: Runtime Error

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

def main():
  n = int(input())
  a = [[] for row in range(200000)]
  C = [int(input()) for i in range(n)]
  b = 0
  d = [0]
  mod = 10 ** 9 + 7
  mini_ans = 0
  for i,c in enumerate(C):
    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)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for row in range(200000)]
C = [int(input()) for i in range(n)]
b = 0
d = [0]
mod = 10 ** 9 + 7
mini_ans = 0
for i,c in enumerate(C):
  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:
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(n)]
c=[cc[0]]
for i in range(1,nn):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
    dp[i]%=mod
    dp[i+1]%=mod
print(dp[n])

Submission status: Runtime Error

Solution code:
n=int(input())
c=[int(input()) for _ in range(n)]
c.insert(0,0)
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
place=[[] for _ in range(n+1)]

for i in range(n+1):
    place[c[i]].append(i)

import bisect
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    col=c[i-1]
    it=bisect.bisect_left(place[col],i-1)
    if it>0:
        j=place[col][it-1]
        if i-1-j>1:
            dp[i]+=dp[j+1]
print(dp[n])

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n=I()
a=[int(input()) for i in range(n)]
dp=[1]+[0]*n
p=[-1]*(1+n)
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    c=a[i-1]
    if p[c]!=-1 and p[c]!=i-1:
        dp[i]+=dp[p[c]]
    p[c]=i
    dp[i]%=mo

print(dp[-1]%mo)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n=I()
a=[int(input()) for i in range(n)]
dp=[1]+[0]*n
p=[-1]*n
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    c=a[i-1]
    if p[c]!=-1 and p[c]!=i-1:
        dp[i]+=dp[p[c]]
    p[c]=i
    dp[i]%=mo

print(dp[-1]%mo)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n=I()
a=[int(input()) for i in range(n)]
dp=[1]+[0]*n
p=[-1]*n
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    c=a[i-1]
    if p[c]!=-1:
        dp[i]+=dp[p[c]]
    p[c]=i
    dp[i]%=mo

print(dp[-1]%mo)

Submission status: Runtime Error

Solution code:
n=int(input())
c=[int(input()) for _ in [0]*n]
l=[-1]*n
dp=[1]*n
l[c[0]]=0
mod=10**+9+7
for i in range(1,n):
	ci=c[i]
	if l[ci] not in [-1,i-1]:
		dp[i]=(dp[i-1]+dp[l[ci]])%mod
	else:
		dp[i]=dp[i-1]
	l[ci]=i
print(dp[n-1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
c=[int(input()) for _ in range(n)]
#g=[[]for _ in range(2*(10**5)+1)]
g=[[] for _ in range(10)]


for i in range(n):
    g[c[i]].append(i)

ans=1
for i in range(len(g)):
    if not g[i]:
        continue
    new=[]
    now=g[i][0]
    cnt=1
    m=1
    for j in range(1,len(g[i])):
        m+=1
        if now+1==g[i][j]:
            cnt+=1
            now+=1
        else:
            now=g[i][j]
            new.append(cnt)
            cnt=1
    new.append(cnt)
    ans2=m*(m-1)//2
    for k in new:
        ans2-=k*(k-1)//2
    ans+=ans2

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
C = [int(input()) for i in range(n)]
nc = 10 ** 5 + 3
mod = 10**9+7

A = [0] * n
B = [-1] * nc

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Submission status: Runtime Error

Solution code:
n = int(input())
C = [int(input()) for i in range(n)]
mod = 10**9+7

A = [0] * n
B = [-1] * (n+1)

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Submission status: Runtime Error

Solution code:

N = int(input())

C = []

for i in range(N):

    c = int(input())

    if len(C) == 0 or C[-1] != c-1:
        C.append(c-1)

lis = []
last = [-1] * N

for i in range(len(C)):

    if i == 0:
        lis.append(1)
    
    elif last[C[i]] == -1 or last[C[i]] == i-1:
        lis.append(lis[-1])

    else:
        lis.append(lis[-1]+lis[last[C[i]]])

    last[C[i]] = i


print (lis[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9+7
P2 = [1]
for i in range(N):
  P2 += [(P2[-1]*2)%MOD]
pre = [-1]*(N+1)
p = -1
end = 0
ans = 1
for i in range(N):
  c = int(input())
  if pre[c]!=-1:
    if p==c:
      continue
    ans += P2[pre[c]]
    end += 1
    pre[c] = end
  else:
    pre[c] = end
  p = c
print(ans%MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9+7
P2 = [1]
for i in range(N):
  P2 += [(P2[-1]*2)%MOD]
pre = [-1]*N
p = -1
end = 0
ans = 1
for i in range(N):
  c = int(input())
  if pre[c]!=-1:
    if p==c:
      continue
    ans += P2[pre[c]]
    end += 1
    pre[c] = end
  else:
    pre[c] = end
  p = c
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, []
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            lr.append([C[c], i])
        C[c] = i
        cp = c
        i += 1
length = i
lr.sort()
hist, add, i, ans = [0] * length, [0] * length, 0, 0
for l, r in lr:
    while i <= l:
        hist[i] = hist[i-1] + add[i]
        ans += add[i]
        i += 1
    add[r] += hist[l] + 1
for i in range(l+1, length):
    ans += add[i]
print((ans+1) % (10**9+7))

Submission status: Runtime Error

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, []
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            lr.append([C[c], i])
        C[c] = i
        cp = c
        i += 1
lr.sort()
hist, add, i, ans = [0] * N, [0] * N, 0, 0
for l, r in lr:
    while i <= l:
        hist[i] = hist[i-1] + add[i]
        ans += add[i]
        i += 1
    add[r] += hist[l] + 1
for i in range(l+1, N):
    ans += add[i]
print(ans+1)

Submission status: Runtime Error

Solution code:
n = int(input(""))
mod = 1e9+7
x = []
f = []
sum = [0 for j in range(0,n+1)]
def add(a,b):
    s = (a+b)%mod
    return s
f.append(1)
x.append(0)
for i in range(1,n+1):
    x.append(int(input()))
    if(x[i]==x[i-1]):
        f.append(f[i-1])
    else :
        f.append(add(f[i-1],sum[x[i]]))
        sum[x[i]]=f[i]
print(int(f[n]))

Submission status: Runtime Error

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for i in range(1,lp):
  l[i] = l[i-1]
  if p[i] in d:
    l[i] += l[p[i]]
  d[p[i]] = i
print(l[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#AGC31 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
c = [I() for _ in range(n)]
dp1,dp2 = [0]*(n+1),[0]*(max(c)+1)
dp1[0] = 1
for i in range(n):
    if dp2[c[i]] == 0:
        dp1[i+1] = dp1[i]
        dp2[c[i]] += dp1[i+1]
        dp2[c[i]] %= mod
    else:
        if c[i] == c[i-1]:
            dp1[i+1] = dp1[i]
            dp2[c[i]] += dp1[i+1]
            dp2[c[i]] %= mod
            continue
        dp1[i+1] += dp1[dp2[c[i]]+1]
        dp1[i+1] += dp1[i]
        dp2[c[i]] += dp1[i+1]
        dp2[c[i]] %= mod
        dp1[i+1] %= mod
print(dp1[-1] % mod)

Submission status: Runtime Error

Solution code:
n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ -1 for i in range(10**5)] 
for i in range(n):
    color = int(input()) - 1

    if color_list[color] not in [-1,i-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7

    color_list[color] = i
print(ans_list[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ [0,-1] for i in range(10**5)] 
for i in range(n):
    color = int(input()) - 1

    if color_list[color][0] > 0 and color_list[color][1] not in [i-1,-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color][1]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7
    
    color_list[color][0] += 1
    color_list[color][1] = i
print(ans_list[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ [0,-1] for i in range(10**5)] 
for i in range(n):
    color = int(input()) - 1
    color_list[color][0] += 1
    if color_list[color][0] > 0 and color_list[color][1] not in [i-1,-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color][1]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7
    color_list[color][1] = i
print(ans_list[-1])

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
dp=[0]*n
dp[0]=1
mod=10**9+7
record={arr[0]:0}
for i,v in enumerate(arr):
  if i==0:
    continue
  dp[i]=dp[i-1]
  if record[v] and record[v]<i-1:
    dp[i]+=dp[record[v]]
    dp[i]=dp[i]%mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

n = int(input())

dp = [0 for i in range(n+1)]


dic = {}

ind = [0 for i in range(n+1)]

for i in range(1,n+1):
    c = int(input())
    if c in dic:
        ind[i] = dic[c][-1]
        dic[c].append(i)
    else:
        dic[c] = [i]

dp[0] , dp[1],dp[2] = 1,1,1

for i in range(3,n+1):
    dp[i] = (dp[i] + dp[i-1]) % MOD
    if(ind[i] == 0):continue
    if(ind[i] == i-1):continue
    dp[i] = (dp[i] + dp[ind[i]]) % MOD

print(dp[n])

Submission status: Runtime Error

Solution code:
N = int(input())
prob = [10**8] + [int(input()) for _ in range(N)]
ans = [0 for _ in range(N + 1)]
ans[0] = 1
for i in range(1, N + 1):
  for j in range(i):
    if prob[j + 1] = prob[i] and prob[j] != prob[i]:
      ans[i] += ans[j]
print(ans[N])

Submission status: Runtime Error

Solution code:
N = int(input())
prob = [10**8] + [int(input()) for _ in range(N)]
ans = [0 for _ in range(N)]
ans[0] = 1
for i in range(1, N + 1):
  for j in range(i):
    if prob[j + 1] = prob[i] and prob[j] != prob[i]:
      ans[i] += ans[j]
print(ans[N])