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: Accepted

Solution code:
N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = [-1]*(2*(10**5)+1)
prevIdx = [0] * N
for i in range(N):
    C[i] = int(input())
    if i > 0 and C[i] == C[i-1]:
        continue
    prevIdx[i] = dic[C[i]]
    dic[C[i]] = i

dp = [0] * N
dp[0] = 1
acc = [0] * N
acc[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1] % mod
    if C[i] == C[i-1] or prevIdx[i] == -1:
        acc[i] = dp[i-1]
        continue
    
    dp[i] += acc[prevIdx[i]]
    acc[i] = acc[prevIdx[i]] + dp[i-1]
    acc[i] %= mod
    dp[i] %= mod

print(dp[N-1] % mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
C = []
last_idx = [0 for i in range(200001)]
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: Accepted

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

n=int(sy())
if n==1:
    print(1)
    quit()
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: Accepted

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

mod = 10 ** 9 + 7

D = []
prev = -1
for ci in C:
    if prev != ci:
        D.append(ci)
        prev = ci

M = len(D)

dic = dict()
dp = [1] * M
for i in range(M):
    if D[i] in dic:
        temp = dp[dic[D[i]]]
        dp[i] = (dp[i - 1] + temp) % mod
    else:
        dp[i] = dp[i - 1]
    dic[D[i]] = i

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
def reversi(N: int, C: list)->int:
    MOD = 10**9 + 7
    dp = [0] * (N+1)
    dp[0] = 1
    lefts = {}
    for i, c in enumerate(C):
        if c in lefts and lefts[c] != i:
            dp[i+1] = (dp[i] + dp[lefts[c]]) % MOD
        else:
            dp[i+1] = dp[i]
        lefts[c] = i+1
    return dp[N]


if __name__ == "__main__":
    N = int(input())
    C = [int(input()) for _ in range(N)]
    ans = reversi(N, C)
    print(ans)

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
C = [I() for i in range(N)]

dic = {}

ans = 0
tmp = "None"
for i in C:
  if i == tmp:
    continue
  else:
    tmp = i
    if i not in dic:
      dic[i] = ans
    else:
      ans += dic[i] + 1
      dic[i] = ans

print((ans+1)%mod)

Submission status: Accepted

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

d = defaultdict(lambda:[])
dd = defaultdict(lambda:{})
dcum = defaultdict(lambda:[0])
for i in range(len(S)):
    d[S[i]].append(i)
    dd[S[i]][i] = len(d[S[i]])-1
    dcum[S[i]].append(0)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = dd[S[i]][i]+1
    dp[i] += dp[i+1]
    dp[i] += dcum[S[i]][j]
    dp[i] %= mod
    dcum[S[i]][j-1] += dp[i+1]+dcum[S[i]][j]
print(dp[0])

Submission status: Accepted

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

l = sorted([(c, i) for i,c in enumerate(C)])

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

for i in range(len(l)-1):
    if l[i][0] == l[i+1][0] and l[i+1][1]-l[i][1] > 1:
        path[l[i][1]].append(l[i+1][1])

dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(N-1):
    for to in path[i]:
        dp[to] = (dp[to]+dp[i])%1000000007

print(dp[N-1])

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

MAX_C = 2 * 10 ** 5


def main():
    N = int(input())
    C = [int(input()) for i in range(N)]
    MOD = 10 ** 9 + 7

    NC = []
    CNT = [0] * (MAX_C+1)
    dp = [0] * (N+1)
    idx = 0
    while idx < N:
        NC.append(C[idx])
        while idx < N - 1 and C[idx] == C[idx+1]:
            idx += 1
        idx += 1

    dp[0] = 1
    for i in range(len(NC)):
        c = NC[i]
        dp[i] = (dp[i]+CNT[c]) % MOD
        dp[i+1] = (dp[i+1]+dp[i]) % MOD
        CNT[c] = dp[i]

    print(dp[len(NC)]%MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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[x[i]]
            #print(res2[x[i]])
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
    res2[x[i]]+=dp[i-1]
    #print(dp,res2)
print((dp[len(x)-1]+1)%(10**9+7))
#print(res)

Submission status: Accepted

Solution code:
N = int(input())
C = [0 for i in range(N)]

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

sosu = 10 ** 9 + 7

dp = [1 for i in range(N)]
alpha = {}
alpha[C[0]] = [0]
mae = C[0]
for i in range(1,N):
    dp[i] = dp[i-1]
    if C[i] != mae:
        if C[i] in alpha.keys():
            length = len(alpha[C[i]])
            lastnum = alpha[C[i]][length - 1]
            dp[i] += dp[lastnum]
            alpha[C[i]].append(i)
        else:
            alpha[C[i]] = [i]
    mae = C[i]
    dp[i] = dp[i] % sosu
print(dp[N-1])

Submission status: Accepted

Solution code:
n = int(input())
z = []
pre = 0
for _ in range(n):
    i = int(input())
    if i != pre:
        z.append(i)
    pre = i
n = len(z)
dp = [1] * (n+1)
dpp = [0] * 2 * 10 ** 5
for i in range(n):
    dp[i+1] = dp[i] + dpp[z[i]-1]
    dpp[z[i]-1] += dp[i]
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
c = [0] * (n + 1)

for i in range(1, n + 1):
    c[i] = int(input())
    
lc = [0] * (2 * 10**5 + 1)
dp = [0] * (n + 1)
dp[1] = 1
lc[c[1]] = 1

for i in range(2, n + 1):
    if lc[c[i]] == i - 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[lc[c[i]]]
    lc[c[i]] = i
    
print(dp[n] % (10**9 + 7))

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dp = [1] * (n + 1)
    a = map(int, stdin, repeat(10, n))
    d = {}
    for i, x in enumerate(a):
        dp[i+1] = dp[i]
        if x in d and d[x] < i:
            dp[i+1] += dp[d[x]]
            if dp[i+1] >= 1000000007:
                dp[i+1] -= 1000000007
        d[x] = i + 1
    print dp[-1]
main()

Submission status: Accepted

Solution code:
def solve(N, Cs):
    counts = [-1 for _ in Cs] + [1]
    latest_c = {}
    ans = 1
    d = 10 ** 9 + 7
    for i, c in enumerate(Cs):
        if c not in latest_c:
            latest_c[c] = i
            counts[i] = ans
        else:
            previous_i = latest_c[c]
            if previous_i != i - 1:
                ans += counts[previous_i]
            latest_c[c] = i
            counts[i] = ans
    return ans % d

if __name__ == "__main__":
    N = int(input())
    Cs = [int(input()) for _ in range(N)]
    print(solve(N, Cs))

Submission status: Accepted

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

MOD = 10 ** 9 + 7
recent = [-1 for _ in range(max(C))]
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: Accepted

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]
m = 10**9+7

dp = [-1] * n
dp[0] = 1
last_dic = {}
for i in range(n):
    if c[i] in last_dic.keys() and i - last_dic[c[i]] >= 2:
        dp[i] = (dp[i-1] + dp[last_dic[c[i]]]) % m
    elif i:
        dp[i] = dp[i-1]
    last_dic[c[i]] = i
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 +7
N = int(input())
C = [input() for _ in range(N)]
dic ={}
lis = [1]
before =C.pop(0)
dic[before]=[0]

for i,s in enumerate(C):
    lis.append(lis[-1])
    if s in dic.keys():
        if s != before:
            lis[-1] += lis[dic[s][-1]+1]
            #for j in dic[s]:
            #    lis[-1] += lis[j]
            dic[s].append(i)
    else:
        dic[s] = [i]
    before = s
    lis[-1] = lis[-1]%mod
print(lis[-1])

Submission status: Accepted

Solution code:
mod = 1000000007

N = int(input())
C = []
for i in range(N):
    c = int(input())
    if i == 0 or C[-1] != c:
        C.append(c)
cases = [1] * (len(C) + 1)
indexes = dict()
for i in range(1, 1 + len(C)):
    c = C[i - 1]
    if c not in indexes:
        cases[i] = cases[i - 1]
    else:
        cases[i] = (cases[i - 1] + cases[indexes[c]]) % mod
    indexes[c] = i
print(cases[len(C)])

Submission status: Accepted

Solution code:
N = int(input())
MODN = int(1e9 + 7)

D = {}
X = [0] * N

for i in range(N):
  c = int(input())
  if not c in D:
    X[i] = 1 if i == 0 else X[i-1]
    D[c] = i
    continue
    
  X[i] = (X[i-1] + X[D[c]]) % MODN if D[c] < i-1 else X[i-1]
  D[c] = i
    
print(X[N-1])

Submission status: Accepted

Solution code:
n = int(input())

mod = 10**9 + 7

dict = dict()
list = []
res = 1
for i in range(n):
  x = input()
  list.append(x)
  if x in dict and list[i - 1] != x:
    res += dict[x]
    dict[x] = res
  elif x not in dict:
    dict[x] = res

print(res % mod)

Submission status: Accepted

Solution code:
n = int(input())
c = [int(input())]
last = [-1 for _ in range(2 * (10 ** 5) + 1)]
for i in range(1, n):
    _c = int(input())
    if _c != c[-1]:  # 連続同数字は1つに連結
        c.append(_c)
# print(c)
out = [0 for _ in range(len(c))]
out[0] = 1
last[c[0]] = 0
for i in range(1, len(c)):
    out[i] = out[i-1]
    if last[c[i]] >= 0:
        # print(out[last[c[i]]])
        out[i] += out[last[c[i]]]
        out[i] %= 10 ** 9 + 7
    last[c[i]] = i
    # print("out:{}".format(out))
    # print("last:{}\n".format(last[:10]))
print(out[-1] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n=int(input())
s=[[]for i in range(2*10**5+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: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    color_dict = {}
    ans = 1
    front_c = 0
    for _ in range(n):
        c = input().rstrip()
        if c != front_c:
            try:
                ans += color_dict[c]
                color_dict[c] = ans
            except KeyError:
                color_dict[c] = ans
            front_c = c
    print(ans%(10**9+7))

Submission status: Accepted

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(2*10**5+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: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
before = [-1] * (2 * 10**5 + 1)
count = [0] * (N + 1)
count[-1] = 1
mod = 10**9 + 7
for i in range(N):
    count[i] = count[i - 1]
    if 0 <= before[C[i]] < i - 1:
        count[i] += count[before[C[i]]]
        count[i] %= mod
    before[C[i]] = i
print(count[N - 1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter, defaultdict

def compress(s):
    ret = []
    for i, si in enumerate(s):
        if i == 0:
            ret.append(si)
        else:
            if si == ret[-1]:
                continue
            else:
                ret.append(si)
                
    return ret

def removeonly1(s):
    cnt = Counter(s)
    ret = []
    
    for si in s:
        if cnt[si] == 1:
            continue
        else:
            ret.append(si)
            
    return ret

n = ni()
c = [ni() for _ in range(n)]
MOD = 10**9+7

colors = removeonly1(compress(c))


dp = [0 for _ in range(len(colors)+1)]

dp[0] = 1
idxs = defaultdict(list)
keys = set()

for i, ci in enumerate(colors):
    dp[i+1] = dp[i]
    
    if ci in keys:
        dp[i+1] += dp[idxs[ci][-1]+1]
        dp[i+1] %= MOD
        
    idxs[ci].append(i)
    keys.add(ci)
        
print(dp[len(colors)])

Submission status: Accepted

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

for x in xrange(1,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: Accepted

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

mod = 10**9 + 7

if n <= 2:
    print(1)
    exit()

# 圧縮
a = [c[0]]
m = 1
for c1, c2 in zip(c, c[1:]):
    if c2 != c1:
        a.append(c2)
        m += 1

memo = [-1] * (2 * 10**5 + 1)
ans = 1
dp = [0] * (m+1)
dp[0] = 1

for i in range(m):
    if memo[a[i]] == -1:
        memo[a[i]] = i
        dp[i+1] = dp[i]
    else:
        idx = memo[a[i]] + 1
        dp[i+1] += dp[i] + dp[idx]
        dp[i+1] %= mod
        memo[a[i]] = i

print(dp[m] % mod)

Submission status: Accepted

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():
    n = I()
    c = IR(n)
    v = [[i+1] for i in range(n-1)]
    v.append([])
    d = defaultdict(deque)
    for i in range(n):
        d[c[i]].append(i)
    for i in d.keys():
        x = None
        while d[i]:
            y = d[i].popleft()
            if x != None and y != x+1:
                v[x].append(y)
            x = y
    path = [0]*(n)
    path[0] = 1
    q = [0]
    while q:
        x = heappop(q)
        for y in v[x]:
            if path[y] == 0:
                heappush(q,y)
            path[y] += path[x]
            path[y] %= mod
    print(path[-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: Accepted

Solution code:
from collections import defaultdict
mod = 10**9 + 7
n = int(input())
prev = None
s = []
d = defaultdict(list)
cnt = 0
for i in range(n):
    c = int(input())
    if prev == c:
        continue
    prev = c
    s.append(c)
    d[c].append(cnt)
    cnt += 1
#print(s)
DP = [0]*cnt
DP[0] = 1
e = {}
for i, c in enumerate(s):
    if i == cnt-1:
        break
    e[c] = e.get(c, 0) + 1
    j = e[c]
    DP[i+1] = (DP[i+1] + DP[i]) % mod
    if j < len(d[c]):
        DP[d[c][j]] = (DP[d[c][j]] + DP[i]) % mod
    #print(DP)
print(DP[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
C = [-1]
for i in range(N):
    c = int(input())
    if c != C[-1]:
        C.append(c)
C = C[1:]
N = len(C)
DP = [1]*N

ixs = defaultdict(lambda: [-1])
ixs[C[0]].append(0)

for i, c in enumerate(C[1:], start=1):
    l = ixs[c][bisect_left(ixs[c], i) - 1]
    if l != -1:
        DP[i] = (DP[i-1] + DP[l])%MOD
    else:
        DP[i] = (DP[i-1])%MOD
    ixs[c].append(i)
print(DP[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = int(1e9) + 7


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)]
    dp = [1] * (N+1)
    last = defaultdict(lambda: -1)
    for i in range(N):
        c = C[i]
        if last[c] != -1 and last[c] != i-1:
            dp[i+1] = (dp[i] + dp[last[c]+1]) % MOD
        else:
            dp[i+1] = dp[i]
        last[c] = i
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
c = [int(raw_input()) for i in range(n)]
mod = 1000000007

dp = [0] * len(c)
last = [-1] * 200001
dp[0] = 1
last[c[0]] = 0
for i in range(1, len(c)):
    dp[i] = dp[i - 1]
    if last[c[i]] >= 0 and last[c[i]] < i - 1:
        dp[i] = (dp[i] + dp[last[c[i]]]) % mod
    last[c[i]] = i

print dp[-1]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
dic={}
c=[0]
for i in range(n):
    t=int(input())
    if c[-1]!=t:
        c.append(t)
g=[[i+1] for i in range(len(c)-1)]
g.append([])
for i in range(len(c)):
    if c[i] in dic:
        g[dic[c[i]]].append(i)
        dic[c[i]]=i
    else:
        dic[c[i]]=i
ans_table=[0 for i in range(len(c))]
ans_table[-1]=1
for i in range(len(c)-1):
    i=len(c)-2-i
    for to in g[i]:
        ans_table[i]+=ans_table[to]
print(ans_table[0]%(10**9+7))

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
dp=[0]*N
idx=dict()
idx[int(input())]=0
dp[0]=1
for i in range(1,N):
    C=int(input())
    if C in idx.keys():
        if idx[C]<i-1:
            dp[i]=(dp[idx[C]]+dp[i-1])%mod
        else:
            dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]
    idx[C]=i
print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

class increment:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

ui = defaultdict(increment())
clists = []
Nc = 0
for i in range(N):
    n = ui[C[i]]
    if n >= Nc:
        clists.append([i])
        Nc += 1
    else:
        clists[n].append(i)

P = [0]*N
Q = [0]*N
Q[0] = 1
QS = [0]*Nc
QS[ui[C[0]]] = 1
for i in range(1,N):
    if C[i] == C[i-1]:
        Q[i] = 0
    else:
        Q[i] = (P[i-1] + Q[i-1]) % M
    
    cind = ui[C[i]]
    P[i] = QS[cind]
    QS[cind] = (QS[cind] + Q[i]) % M

print((P[N-1]+Q[N-1]) % M)

Submission status: Accepted

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

n=int(input())
c = [int(input()) for i in range(n)]

r = [-1]*n
d=dict()
for i, cc in enumerate(c):
    if cc in d:
        r[i] = d[cc]
        d[cc] = i
    else:
        d[cc] = i

#print(c)
#print(r)
dp=[1]*n
dp[0]=1
for i in range(1,n):
    if r[i] == -1:
        dp[i] = dp[i-1]
    elif r[i] == i-1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1] + dp[r[i]])%(10**9+7)

#print(dp)
print(dp[n-1])

Submission status: Accepted

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]*(2*10**5)
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: Accepted

Solution code:
import sys,bisect

sys.setrecursionlimit(10000000)
N = int(input())
C = [int(input()) for _ in range(N)] #color
v = 10**9+7
from collections import defaultdict
d = defaultdict(list)
for i,c in enumerate(C):
    d[c].append(i)


def guchoku(l):
    assert isinstance(l,list)
    if len(l) <=2:
        return 1
    top_coor = l[0]
    if top_coor in l[1:] and l[0] != l[1]:
        _index= l[1:].index(top_coor)
        return guchoku(l[_index+1:])+ guchoku(l[1:])
    return guchoku(l[1:])

cache = dict()
cache[N] = 1
cache[N-1] = 1
cache[N-2] = 1

def check(i):
    index = bisect.bisect_left(d[C[i]],i+1)

    if index==len(d[C[i]]):
        return -1
    # print(i, d[C[i]] ,d[C[i]][index])
    return d[C[i]][index]

def guchoku_i(i):
    # print("hoge",i,d[C[i]])
    if i<0:
        raise
    if i in cache:
        return cache[i]
    c = check(i)
    if C[i] != C[i+1] and c !=-1 :
        cache[i]= guchoku_i(i+1) + guchoku_i(c) %v
        return cache[i]
    cache[i]=  guchoku_i(i+1) %v
    return cache[i]

# print(guchoku(C))
print(guchoku_i(0)%v )

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7
subC = [-2] * (2 * 10 ** 5 + 10)
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] < 0 or cntC[i] == i:
        dp[i + 1] = dp[i] % MOD
    else:
        dp[i + 1] = (dp[i] + dp[cntC[i]]) % MOD


print(dp[N])

Submission status: Accepted

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

dp = [0 for i in range(n)]
dp[0] = 1
memo = {c[0]:0}
for i in range(1,n):
    if c[i] in memo:
        if memo[c[i]] != i-1:
            dp[i] =(dp[i-1] + dp[memo[c[i]]])%mod
            memo[c[i]] = i
        else:
            dp[i] = dp[i-1]
            memo[c[i]] = i
    else:
        dp[i] = dp[i-1]
        memo[c[i]] = i

print(dp[n-1])

Submission status: Accepted

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

p = [0 for _ in range((2 * 10**5) + 1)]
dp = [0 for _ in range(N)]
p[C[-1]] = -1
dp[-1] = 1
for i in range(2, N + 1):
    if p[C[-i]] == 0 or p[C[-i]] == -i + 1:
        dp[-i] = dp[-i + 1]
    else:
        dp[-i] = (dp[-i + 1] + dp[p[C[-i]]]) % (10**9 + 7)
    p[C[-i]] = -i

ans = dp[0]
print(ans)

Submission status: Accepted

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

A = []
for c in C:
    if A and A[-1]==c: continue
    A.append(c)

last = [-1] * 200001
B = [-1] * len(A)
for i,a in enumerate(A):
    B[i] = last[a]
    last[a] = i

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

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
C = []
prev = None
for i in range(n):
	tmp = int(input())
	if tmp==prev:
		n -= 1
		continue
	else:
		C.append(tmp)
		prev = tmp
dp = [0]*n
dp[0] = 1
table = {C[0]:1}

for i in range(n-1):
	if C[i+1] not in table:
		table[C[i+1]]= 0 
	dp[i+1] = dp[i] + table[C[i+1]]  
	table[C[i+1]] += dp[i]
	dp[i+1] %= mod
	table[C[i+1]] %= mod

print(dp[n-1])

Submission status: Accepted

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]*(2*10**5+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: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
mod = 10**9+7
dp = [0]*(n+1)
mae = [-2]*(max(a)+1)
mae2 = [0]*(max(a)+1)
dp[0] = 1
for i in range(n):
        if mae[a[i]] != -2 and mae[a[i]] != i-1:
                dp[i+1] = dp[i] + mae2[a[i]]
        else:
                dp[i+1] = dp[i]
        dp[i+1] %= mod
        if mae[a[i]] == i-1:
                mae[a[i]] = i
                continue
        mae[a[i]] = i
        mae2[a[i]] += dp[i]
        mae2[a[i]] %= mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict


def main():
    # n,m = [int(z) for z in input().split()]
    # table =[
    #     [int(z) for z in input().split()]
    #     for _ in range(n)
    # ]
    V = 10 ** 9 + 7
    n = int(input())
    c = [int(input()) for _ in range(n)]

    table = [0] * (n + 1)
    table[0] = 1

    D = defaultdict(lambda: 0)

    for i in range(n):
        ci = c[i]
        if i != 0:
            if c[i - 1] == ci:
                table[i + 1] = table[i] % V
                continue

        res = table[i]
        pre = D[ci]
        res += pre
        table[i + 1] = res % V

        D[ci] = D[ci] + table[i] % V

    print(table[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


fin = sys.stdin.readline
MOD = 10**9 + 7
N = int(fin())
C_list = tuple(int(fin()) for _ in range(N))

dp = [0] * N
dp[0] = 1
past_idx = {C_list[0]: 0}
for i, C in enumerate(C_list[1:], start=1):
    if C in past_idx:
        dp[i] = dp[i - 1] + dp[past_idx[C]] if i - past_idx[C] > 1 else dp[i - 1]

    else:
        dp[i] = dp[i - 1]
    past_idx[C] = i
    dp[i] %= MOD
# print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
C = []
for i in range(N):
    c = int(input())-1
    if not C or C[-1] != c:
        C.append(c)
N = len(C)

prev = [None]*(max(C)+1)

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

for i,c in enumerate(C):
    if prev[c] is None:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i] + dp[prev[c]+1]
    dp[i+1] %= MOD

    prev[c] = i

print(dp[N])

Submission status: Accepted

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

dp = [0 for _ in range(N)]
dp[0] = 1

MOD = 10**9 + 7

r = [-1 for _ in range(N)]
prev = [-1 for _ in range(max(C) + 1)]

for i in range(N):
    if prev[C[i]] != -1 and prev[C[i]] + 1 != i:
        r[prev[C[i]]] = i
    prev[C[i]] = i

for i in range(N - 1):
    if r[i] != -1:
        dp[r[i]] += dp[i]
        dp[r[i]] %= MOD
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD

print(dp[N-1] % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
c = [int(input()) for _ in range(n)]
d = [c[0]]
for i in range(1, n):
	if c[i] != d[-1]:
		d.append(c[i])
#print(d)
n = len(d)
rightmost = [-1] * 200001
seg = []
for i in range(n):
	if rightmost[d[i]] >= 0:
		seg.append([rightmost[d[i]], i])
	rightmost[d[i]] = i

#print(seg)
dp = [1 for _ in range(n)]
M = len(seg)
cnt = 0
for i in range(1, n):
	if cnt == M:
		dp[i] = dp[i-1]
	elif i == seg[cnt][1]:
		dp[i] = dp[i-1] + dp[seg[cnt][0]]
		cnt += 1
	else:
		dp[i] = dp[i-1]
	dp[i] %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from cStringIO import StringIO
from collections import Counter

range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = StringIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10**9 + 7
MODF = float(MOD)

MAGIC = 6755399441055744.0
SHRT = 65536.0

MODF_INV = 1.0 / MODF
SHRT_INV = 1.0 / SHRT

fround = lambda x: (x + MAGIC) - MAGIC
fmod = lambda a: a - MODF * fround(MODF_INV * a)
fmul = lambda a, b, c=0.0: fmod(fmod(a * SHRT) * fround(SHRT_INV * b) + a * (b - SHRT * fround(b * SHRT_INV)) + c)


def main():
    n = int(input())
    c = [int(input()) for _ in range(n)]

    _c, prev = [], 0
    for i in range(n):
        if c[i] != prev:
            _c.append(c[i])
        prev = c[i]
    c = _c
    n = len(c)

    prev_occur = [0] * (2 * 10**5 + 1)
    res, counts = [1.0] * (n + 1), Counter()
    for i in range(n):
        ind = prev_occur[c[i]]
        if ind != 0:
            res[i + 1] = fmod(res[i] + res[ind])
        else:
            res[i + 1] = res[i]

        counts[c[i]] += 1
        prev_occur[c[i]] = i + 1

    print(int(res[-1]) % MOD)


if __name__ == '__main__':
    main()