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:
N = int(input())
C = [int(input()) for _ in range(N)]

MOD = 10 ** 9 + 7
recent = [-1 for _ in range(N)]
hist = []

ans = 1
for i in range(N):
    c = C[i] - 1
    if recent[c] >= 0 and recent[c] != i-1:
        ans = (ans + hist[recent[c]]) % MOD
    recent[c] = i
    hist.append(ans)
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
l  = []
for i in range(0, N):
l.append(input())

if N >= 6:
    print(5)
else:
    print(3)

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
a = []
b = []
for i in range(n-2):
    if c[i] in c[i+2:]:
        tmp = c[i+2:].index(c[i])
        a.append(i)
        b.append(tmp+i+2)
cnt = 0
final = a[-1]
dp=[-1]*(n)

for i in range(n)[::-1]:
    if i>final:
        dp[i] = 1
        continue
    if i in a:
        end = b[a.index(i)]
        dp[i] = dp[i+1] + dp[end]
    else:
        dp[i] = dp[i+1]


print(dp[0]%(10**9+7))

Submission status: Runtime Error

Solution code:
N = int(input())
l  = []
l.append(input())
for i in range(1, N):
    if li[i] != input():
        l.append(li[i])

if N >= 6:
    print(5)
else:
    print(3)

Submission status: Runtime Error

Solution code:
mo = 10 ** 9 + 7

n = int(input())
cs = [int(input()) for _ in range(n)]

def compress(xs):
    return [xs[0]] + [x for px, x in zip(xs, xs[1:]) if px!=x]

cs = compress(cs)

c2idx = [[] for _ in range(n)]
for i,c in enumerate(cs):
    c2idx[c].append(i)

dp = [0] * (len(cs) + 1)
dp[0] = 1
for i, c in enumerate(cs):
    dp[i] %= mo
    for nc_idx in c2idx[c]:
        dp[nc_idx + 1] += dp[i]
    c2idx[c].pop(0)

# print(cs)
# print(dp)
print(dp[-1] % mo)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for row in range(200000)]
b = 0
d = [0]
mini_ans = 0
for i in range(n):
  c = int(input())
  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())
s=[[]for i in range(n+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
for i in range(n):
    c.append(int(input()))

def f(x):
    if x == 0:
        return 1
    if x == 1:
        return 1
    a = 0
    b = []
    for i in range(x):
        if c[i] == c[x - 1]:
            b.append(i)
            if len(b) == 1 or i != b[-2] + 1:
                a += f(i)
                a %= 10 ** 9 + 7
    return a

print(f(n))

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
for i in range(n):
    c.append(int(input()))

def f(x):
    if x == 0:
        return 1
    if x == 1:
        return 1
    a = 0
    b = []
    for i in range(x):
        if c[i] == c[x - 1]:
            b.append(i)
            if len(b) == 1 or i != b[-2] + 1:
                a += f(i)
    return a

print(f(n))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
import bisect
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
for i in range(len(S)):
    d[S[i]].append(i)

val = [0]*(len(S)+1)
val[-1]=1
def rec(n):
    if val[n] != 0:
        return val[n]
    s = S[n]
    res = rec(n+1)
    l = d[s]
    i = bisect.bisect(l,n)
    for j in range(i,len(l)):
        res += rec(l[j]+1)
        res %= mod
    val[n]=res
    return res
print(rec(0))

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]
            color[i-1] = ans
        j = i
        if ans >= (10**9+7):
            ans = ans %(10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 20:36:58 2019

@author: Yamazaki Kenichi
"""

N = int(input())
C = [int(input()) for i in range(N)]
mod = 10**9+7
T = [[0] for i in range(N+1)]
ans = [1 for i in range(N+1)]
for i in range(N): 
    if i == 0 or C[i] != C[i-1]:
        T[C[i]][0] += 1
        T[C[i]].append(i)
        if T[C[i]][0] >=2:
            ans[i] = (ans[i-1] + ans[T[C[i]][-2]])%mod
        else:
            ans[i] = ans[i-1]%mod
    else:
        ans[i] = ans[i-1]%mod
        
print(ans[N-1]%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
a=""
for i in range(n):
    k=input()
    l.append(k)
    a+=k
li=[a]
i=0
while True:
    k=len(set(li))
    for v in range(n):
        for i in range(v,n):
            if a[v]==a[i]:
                li.append(a[:v]+a[v]*(i+1-v)+a[i+1:])
    if k==len(set(li):
        print(k)
        break

Submission status: Runtime Error

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

DIV = 10**9+7

def make2d_arr(w,h,val =INF):
    return [[val]*w for i in xrange(h)]

def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs

N = int_raw()
C =[]
dp = [0 for i in xrange(N)]

m_prev = {}
prevs = [-1 for i in xrange(N)]

for i in xrange(N):
    c = int_raw()
    C.append(c)
    if c in m_prev:
        prevs[i] = m_prev[c]
        m_prev[c]= i
    else:
        m_prev[c]=i
    
dp[0] =1
dp[1] =1

for x in xrange(2,N):
    cx = C[x]
    dp[x] = dp[x-1]
    if cx == C[x-1]:
        continue
    y = prevs[x]
    if y != -1:
        dp[x]+=dp[y]
        dp[x]= dp[x]%DIV        
    """for y in xrange(x-2,-1,-1):
        cy = C[y]
        if cx == cy:
            dp[x]+=dp[y]
            dp[x]= dp[x]%DIV
            break"""

print dp[-1]

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
a = []
b = []
for i in range(n-2):
    if c[i] in c[i+2:]:
        tmp = c[i+2:].index(c[i])
        a.append(i)
        b.append(tmp+i+2)
cnt = 0
stop = a[-1]
def func(start):
    if start>stop:
        return 1
    if start in a:
        end = b[a.index(start)]
        return func(end) + func(start+1)
    else :
        return func(start+1)
    

print(func(0))

Submission status: Runtime Error

Solution code:
n = int(input())
j = 0
ans = 1
color = [-1 for i in range(n)]
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]
            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 sys import stdin
input = stdin.readline

n = int(input())
L = []
dplist = [1]
last = 0

for i in range(n):
    c = int(input())
    L.append(c)
    if c == last:
        dplist.append(dplist[i])
        continue
    last = c
    re = 0
    for j in range(i-1):
        if L[j] == c:
            re += dplist[j]
    dplist.append(dplist[i]+re)

print(dplist[-1] % (10**9 + 7)

Submission status: Runtime Error

Solution code:
import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

toAns = 10 ** 9 + 7
dic = {}
N = int(input())
for i in range(N):
    n = int(input())
    dic.setdefault(n, [])
    try:
        las = dic[n][-1]
        if las + 1 < i:
            dic[n].append(i)
        else:
            dic[n][-1] = i
    except:
        dic[n].append(i)
#print(dic)
ans = 1
for k, v in dic.items():
    if len(v) >= 2:
        ans += int(nCr(len(v), 2))
#print(ans)
for i, k in enumerate(dic.keys()):
    v = dic[k]
    for j, kk in enumerate(dic.keys()):
        if j <= i:
            continue
        vv = dic[kk]
        if sum(v) < sum(vv):
            left = v
            right = vv
        else:
            left = vv
            right = v
        if max(left) < min(right):
            ans += 1
print(ans % toAns)

Submission status: Runtime Error

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

DIV = 10**9+7

def make2d_arr(w,h,val =INF):
    return [[val]*w for i in xrange(h)]

def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs

N = int_raw()
C =[]
dp = [0 for i in xrange(N)]

for i in xrange(N):
    c = int_raw()
    C.append(c)
dp[0] =1
dp[1] =1

for x in xrange(2,N):
    cx = C[x]
    dp[x] = dp[x-1]
    if cx == C[x-1]:
        continue
    for y in xrange(x-2,-1,-1):
        cy = C[y]
        if cx == cy:
            dp[x]+=dp[y]
            dp[x]= dp[x]%DIV
            break

print dp[-1]

Submission status: Runtime Error

Solution code:
mo = 10 ** 9 + 7
inf = 1 << 60

n = int(input())
cs = [int(input()) for _ in range(n)]

def compress(xs):
    return [xs[0]] + [x for px, x in zip(xs, xs[1:]) if px!=x]

cs = compress(cs)
c2idx = {}
for i,c in enumerate(cs):
    if c not in c2idx:
        c2idx[c] = [i]
    else:
        c2idx[c].append(i)

memo = [inf]*(len(cs) + 3)

def count_reversi(idx):
    if idx >= len(cs):
        return 1
    if memo[idx] != inf:
        return memo[idx]
    res = 0
    c = cs[idx]
    for nc_idx in reversed(c2idx[c]):
        if nc_idx <= idx:
            break
        res += count_reversi(nc_idx+1)
    res += count_reversi(idx+1)   
    res %= mo
    memo[idx] = res
    return res

print(count_reversi(0))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    ans = 1
    for i in d.keys():
        ans *= d[i]+1
        ans %= mod
    print(ans-1)
#B
def B():
    def dfs(n):
        if n == 0:
            return 1
        res = 0
        for i in v[n]:
            res += dfs(i)
        return res
    n = I()
    c = IR(n)
    v = [[i-1] for i in range(n)]
    d = defaultdict(deque)
    for i in range(n):
        d[c[i]].append(i)
    for i in d.keys():
        d[i] = deque(d[i])
        x = None
        while d[i]:
            y = d[i].popleft()
            if x != None and y != x+1:
                v[y].append(x)
            x = y
    memo = [None]*(n+1)
    memo[0] = 1
    print(dfs(n-1))
#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Runtime Error

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

for i in range(n - 1, 0, -1):
    if C[i] == C[i - 1]:
        del C[i]

D = [0] * n
for i in range(2, n):
    D[i] = D[i - 1] + i - 1
        
ans = 1
for i in Counter(C).values():
    ans += D[i]
    
print(ans % mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
c = [int(input()) for i in range(n)]

ans = 1
li = [[] for i in range(9)]
for i in range(n):
  if not li[c[i]]:
    li[c[i]].append(i)
  else:
#    if li[c[i]] != li[c[i]][-1]

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

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
c = [int(input()) for i in range(n)]

ans = 1
li = [[] for i in range(9)]
for i in range(n):
  if not li[c[i]]:
    li[c[i]].append(i)
    print(i)
  else:
#    if li[c[i]] != li[c[i]][-1]

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

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
Ca = [int(input())-1 for i in range(N)]
C = []
p = -1
for c in Ca:
    if p != c:
        C.append(c)
    p = c
#print(C)
N = len(C)
if N<=2:
    print(1)
    exit()
L = [-1]*N
dp = [0]*N
dp[0] = 1
L[C[0]] = 0


for i, c in enumerate(C[1:], 1):
    if L[c] == -1:
        L[c] = i
        dp[i] = dp[i-1]
        continue
    else:
        dp[i] = (dp[i-1] + dp[L[c]]) % mod
        L[c] = i
print(dp[-1])

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
Ca = [int(input())-1 for i in range(N)]
C = []
p = -1
for c in Ca:
    if p != c:
        C.append(c)
    p = c
#print(C)
N = len(C)
L = [-1]*N
dp = [0]*N
dp[0] = 1
L[C[0]] = 0

if N<=2:
    print(1)
    exit()
for i, c in enumerate(C[1:], 1):
    if L[c] == -1:
        L[c] = i
        dp[i] = dp[i-1]
        continue
    else:
        dp[i] = (dp[i-1] + dp[L[c]]) % mod
        L[c] = i
print(dp[-1])

Submission status: Runtime Error

Solution code:

mod = 10**9+7
N = int(input())
Ca = [int(input())-1 for i in range(N)]
C = []
p = -1
for c in Ca:
    if p != c:
        C.append(c)
    p = c
#print(C)
N = len(C)
L = [-1]*N
dp = [0]*N
dp[0] = 1
L[C[0]] = 0

for i, c in enumerate(C[1:], 1):
    if L[c] == -1:
        L[c] = i
        dp[i] = dp[i-1]
        continue
    else:
        dp[i] = (dp[i-1] + dp[L[c]]) % mod
        L[c] = i
print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
subC = [-2] * (2 * 10 ** 5)
cntC = [-1]*N
for num, i in enumerate(C):
    cntC[num] = subC[i]+1
    subC[i] = num

# print(cntC)

dp = [0] * (N + 10)
dp[0] = 1
for i in range(N):
    if cntC[i] == -1 or cntC[i] == i:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[cntC[i]]


print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
Ca = [int(input())-1 for i in range(N)]
C = []
p = -1
for c in Ca:
    if p != c:
        C.append(c)
    p = c
#print(C)
N = len(C)
L = [-1]*N
dp = [0]*N
dp[0] = 1
L[C[0]] = 0

for i, c in enumerate(C[1:], 1):
    if L[c] == -1:
        L[c] = i
        dp[i] = dp[i-1]
        continue
    else:
        dp[i] = dp[i-1] + dp[L[c]]
        L[c] = i
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(2*10**5+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Submission status: Runtime Error

Solution code:
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(N+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Submission status: Runtime Error

Solution code:
N = int(input())
DP = [0] * (N+1)
DP[0] = 1
su = [0] * (2*(10**5))
prev = None
for i in range(N):
    C = int(input())
    if prev == C:
        DP[i+1] = DP[i]
    else:
        su[C] += DP[i]
        DP[i+1] = su[C]
    prev = C
print(DP[N])

Submission status: Runtime Error

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

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

AL=[[] for i in range(N+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Submission status: Runtime Error

Solution code:
N = int(raw_input())
C = []

for i in range(N):
    C.append(int(raw_input()))

S = 0
i = 0
while i < N:
    j = i+1
    while j < N:
        if C[i] == C[j] and C[i]!=flag:
            S += 1
            flag = C[i]
        else:
            flag = -1
        j += 1
    i += 1

print S+1

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]

dp = [0]*(n+1)

dp[1] = dp[2] = 1

for i in range(3, n+1):

  dp[i] = dp[i-1] + sum(c[j]==c[i-1] for j in range(i-1))
  if c[i-1] == c[i-2]:
  	dp[i] -= 1


print(dp[n]%(10**9+7))

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]

dp = [0]*(n+1)

dp[1] = dp[2] = 1

for i in range(3, n+1):

  dp[i] = dp[i-1] + sum(c[j]==c[i-1] for j in range(i-1))
  if c[i-1] == c[i-2]:
  	dp[i] -= 1


print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]

dp = [0]*(n+1)

dp[1] = dp[2] = 1

for i in range(3, n+1):
  if c[i] == c[i-1]:
  	dp[i] = dp[i-1]
  else:
    dp[i] = dp[i-1] + sum(c[j]==c[i] for j in range(i))
print(dp[n])