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:
#!/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()
    m = 2 * 10 ** 5
    c = [m] + IR_(n) + [m]
    dp0 = [0] * (n + 1)
    dp1 = [0] * (m + 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: Accepted

Solution code:
import bisect

MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cldic={}
dp=[0]*(N2-1)+[1]
for i in range(N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  if c in cldic:
    dp[i]+=dp[cldic[c]]      
  cldic[c]=i
    
#print(dp)
print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
import bisect

MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]

  if len(cdic[c])>0:
    ind=bisect.bisect_left(cdic[c],i)
    if ind>0:
      dp[i]+=dp[cdic[c][ind-1]]
      #print(cdic[c],i,ind-1)
    
#print(dp)
print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  if len(cdic[c])<5:
    for j in reversed(cdic[c]):
      if j<i:
        dp[i]+=dp[j]
        break
  else:
    l,r=0,len(cdic[c])
    while(l<=r):
      mid=(l+r)//2
      if cdic[c][mid]<i and cdic[c][mid+1]>=i:
        dp[i]+=dp[cdic[c][mid]]
        break
      elif cdic[c][mid]>=i:
        r=mid-1
      elif cdic[c][mid+1]<i:
        l=mid+1
      else:
        print("error")
    
#print(dp)
print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
c = [int(input())]
for _ in range(n-1):
    x = int(input())
    if x != c[-1]: c.append(x)
n = len(c)
t = [-1] * (10**5*2+1)
t[c[0]] = 0
dp = [1] + [0] * (n-1)

for i in range(1, n):
    dp[i] += dp[i-1]
    if t[c[i]] != -1:
        dp[i] += dp[t[c[i]]]
    dp[i] %= MOD
    t[c[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
l = [int(input()) for _ in range(N)]
dp = [0] * (N+1)
pos = defaultdict(lambda: -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: Accepted

Solution code:
mod = 10**9+7
from collections import defaultdict
N = int(input())
C = defaultdict(list)
dp = [1] * N
for i in range(N):
    col = int(input())
    dp[i] = dp[i-1]
    if not len(C[col]) == 0:
        if not C[col][-1] + 1 == i:
            dp[i] = (dp[C[col][-1]] +dp[i])%mod
    C[col].append(i)
print(dp[N-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def main():
    n = int(input())
    c = [int(input()) for _ in range(n)]
    d = []
    d.append(c[0])
    for i in range(1, n):
        if c[i] != d[len(d)-1]:
            d.append(c[i])
    lst = [-1]*(2*10**5+1)
    dp = [0]*len(d)
    dp[0] = 1
    lst[d[0]] = 0
    for i in range(1, len(d)):
        if lst[d[i]] == -1:
            lst[d[i]] = i
            dp[i] += dp[i-1]
        else:
            dp[i] += dp[i-1] + dp[lst[d[i]]]
            lst[d[i]] = i
        dp[i] %= MOD
    print(dp[len(d)-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
C = []
mod = 10**9+7
for i in range(n):
    c = int(input())
    if i==0:
        C.append(c)
    elif C[-1]!=c:
        C.append(c)
n = len(C)
dp = [0]*n
idx = {}
for i in range(n):
    if i==0:
        idx[C[i]] = i
        dp[i] = 1
    else:
        if C[i] not in idx:
            dp[i] = dp[i-1]
            idx[C[i]] = i
        else:
            dp[i] = dp[i-1]+dp[idx[C[i]]]
            idx[C[i]] = i
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7

s = [0 for _ in range(2*10**5)]
pos = [-1 for _ in range(2*10**5)]
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[-1] = 1

for i in range(n):
	x = int(input())
	if i == 0:
		dp[0] = 1
	else:
		p = pos[x - 1]
		if p == i - 1:
			dp[i] = dp[i - 1]
		elif p > -1:
			dp[i] = dp[i - 1] + dp[p]
			dp[i] %= mod
		else:
			dp[i] = dp[i - 1]
	pos[x - 1] = i
print(dp[n - 1])

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7

stone = [0 for _ in range(2*10**5)]
stone_last_pos = [-1 for _ in range(2*10**5)]

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

for i in range(n):
    c = int(input())
    if i == 0:
        dp[0] = 1
    else:
        p = stone_last_pos[c-1]
        if p == i-1:
            dp[i] = dp[i-1]
        elif p > -1:
            dp[i] = dp[i-1] + dp[p]
            dp[i] %= mod
        else:
            dp[i] = dp[i-1]
    stone_last_pos[c-1] = i

print(dp[n-1])

Submission status: Accepted

Solution code:
d={i:0for i in range(1<<18)};c=0;r=1
for _ in[0]*int(input()):m=int(input());r+=d[m]*(c!=m);d[m]=r;c=m
print(r%(10**9+7))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
mod = 10 ** 9 + 7

c = []

for i in range(n):
    c.append(int(input()))

d = {}
dp = [[1,0]]

p = -1
for ci in c:
    if p != ci:
        cnt = 0
        if ci in d:
            cnt = sum(dp[d[ci]]) % mod
        dp.append([sum(dp[-1]) % mod, cnt])
        d[ci] = len(dp) - 1
    p = ci

print(sum(dp[-1]) % mod)

Submission status: Accepted

Solution code:
from itertools import groupby
from collections import defaultdict

mod = 10**9+7
N = int(input())
C = [int(input()) for _ in range(N)]
C = [k for k, g in groupby(C)]
num = defaultdict(int)
dp = [1] + [0] * len(C)
for i, c in enumerate(C):
    dp[i+1] = num[c] = (dp[i] + num[c]) % mod
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import groupby

read = sys.stdin.read

N, *C = map(int, read().split())
C = [i for i, _ in groupby(C)]
mod = 10 ** 9 + 7
cnt = defaultdict(int)
dp = 1
for i in C:
    prev = dp
    dp = (cnt[i] + dp) % mod
    cnt[i] = (cnt[i] + prev) % mod

print(dp)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import groupby

read = sys.stdin.read

N, *C = map(int, read().split())
C = [i for i, _ in groupby(C)]
mod = 10 ** 9 + 7
cnt = defaultdict(int)
dp = 1
for idx, i in enumerate(C):
    prev = dp
    dp = (cnt[i] + dp) % mod
    cnt[i] = (cnt[i] + prev) % mod

print(dp)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
stones = [int(input()) for _ in range(N)]
dp = [0] * (N+1)
rightmost = [0] * (2 * 10**5 + 1)
dp[0] = 1
for i, c in enumerate(stones):
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    if rightmost[c] not in [0, i]:
        dp[i+1] += dp[rightmost[c]]
        dp[i+1] %= MOD
    rightmost[c] = i+1
print(dp[N])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    C=LIN(N)
    RLE = []
    for c in C:
        if not RLE or RLE[-1]!=c-1:
            RLE.append(c-1)
    
    N=len(RLE)
    cumsum = [0]*(2*(10**5))
    DP = [1]+[0]*N

    for i,c in enumerate(RLE):
        DP[i+1] += DP[i]
        DP[i+1] += cumsum[c]
        cumsum[c] += DP[i]
        DP[i+1]%=mod
    print(DP[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

l=[0]*2*10**5#ペアを作れるか診断
k=[0]*2*10**5#ansを記録

ans=1
pre=-1
for _ in range(N):
    c=int(input())-1
    if pre==c:
        continue
    l[c]+=1
    ans+=k[c]*min(l[c]-1,1)
    k[c]=ans
    pre=c
    """
    print(c+1)
    print(l[:5],k[:5])
    print(ans)
    """
print(ans%(10**9+7))

Submission status: Accepted

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]+=dp[N-i]
print(dp[0])

Submission status: Accepted

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

def main():
    N,*C=map(int, open(0).read().split())
    DP=[Fp(1)]*(N+1)
    prev={}
    for i,c in enumerate(C):
        d=DP[i]
        if c in prev and not (i and C[i-1]==c):
            d+=DP[prev[c]]
        prev[c]=i+1
        DP[i+1]=d
    print(DP[N])

if __name__ == "__main__":
    main()

Submission status: Accepted

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
mod=10**9+7
before=[0 for i in range(2*10**5+1)]

for i in range(n):
    a=lists[i]
    if before[a]==0:
        dp[i+1]=dp[i]
        before[a]=i+1
        continue
        
    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]])%mod

            before[a]=i+1
print(dp[n]%mod)

Submission status: Accepted

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

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

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {}
    pre = -1
    for n in range(N):
        c = int(input())
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue
        r = D.setdefault(c, 0)
        dp[n + 1] = (dp[n + 1] + r) % mod
        D[c] = r + dp[n]
        pre = c
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
C=[int(input()) for _ in range(N)]
C=[0]+[c for i,c in enumerate(C) if i==0 or C[i-1]!=c]
MOD=10**9+7

#dp[i]=インデックスiまででの塗り方の数
dp=[0]*(len(C))
dp[0]=1
import collections
memo=collections.defaultdict(int)
for i in range(1,len(dp)):
    dp[i]=(dp[i-1]+memo[C[i]])%MOD
    memo[C[i]]=(memo[C[i]]+dp[i-1])%MOD

print(dp[len(C)-1])

#print(dp)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
c = []
e = [0]*200001
x = [0]*200001
for i in range(n):
    c.append(inn())
ddprint(c)
x[0] = 1
e[c[0]] = 1
for i in range(1,n):
    if c[i]==c[i-1]:
        x[i] = x[i-1]
        continue
    x[i] = (x[i-1]+e[c[i]])%R
    e[c[i]] += x[i-1]
    #ddprint(x[:8])
    #ddprint(e[:8])
print(x[n-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
tmp = [int(input()) for _ in range(N)]
mod = 10 ** 9 + 7
C = []
for c in tmp:
    if not C:
        C.append(c)
        continue
    if C[-1] != c:
        C.append(c)
N = len(C)

last = defaultdict(int)
ans = 1

for c in C:
    ans += last[c]
    ans %= mod
    last[c] = ans

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
C = Line(N,1)

last = defaultdict(lambda:-1)

dp = [0]*N
dp[0] = 1
last[C[0]] = 0

for i in range(1,N):
    if C[i]==C[i-1]:
        dp[i] = dp[i-1]
    else:
        if last[C[i]]>=0:
            dp[i] = (dp[i-1] + dp[last[C[i]]])%mod
        else:
            dp[i] = dp[i-1]
    last[C[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
c=[int(input()) for i in range(n)]
dp=[0]*n
dic={}
dp[0]=1
dic[c[0]]=1
for i in range(1,n):
    if c[i]==c[i-1]:
        dp[i]=dp[i-1]
        continue
    if c[i] in dic:
        dp[i]=(dp[i-1]+dic[c[i]])%mod
        dic[c[i]]=dp[i]
    else:
        dp[i]=dp[i-1]%mod
        dic[c[i]]=dp[i]
print(dp[-1]%mod)
# print(dic)

Submission status: Accepted

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


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

mod = 10**9+7

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

for i, a in enumerate(A):
    ind = last_ind[a]
    if ind == -1 or ind == i-1:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = (dp[i] + dp[ind+1] + 1) % mod
    last_ind[a] = i

print((dp[N]+1)%mod)

Submission status: Accepted

Solution code:

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

# 左からi番目までの石を見ていくときに何通りの列ができるか
dp = [0] * N
# 一通りはあるので１
dp[0] = 1

# ある色が最後にどこで出てきたか覚えておく
last = dict()




for i,c in enumerate(C):
    if i == 0:
        last[c] = i
    else:
        dp[i] = dp[i-1]
        """

        たとえば
        112212121222
        のi=8（一番右にある1）を見ているとき、i=8の石を選んで間をひっくり返すか返さないかの選択肢がうまれる。
        その時増える起こりうる列の数は、最後の1が出てきたところから左について、何通りの列を作るれかに依存する。
        11111112 1222
        11222212 1222
        11221212 1222
        みたいなパターンがあり、i=8の1を選んでひっくり返すか、そのままにしておくかの選択の余地が生まれる。
        
        なので、
        ・最後に同じ数字が出てきた場所を覚えておく。
        ・そこまでのdpを今のdpに加える（i番目の石を選んでひっくり返す場合、最後にiと同じ色が出てきたところの手前のとりうる列の数だけ新たに列を作ることができるため）
        を繰り返せば、最終的な数が求まる

        """
        # cが既に出てきていて、さらに今見ている石と隣り合っていない場合
        if c in last and last[c] < i-1:
            dp[i] += dp[last[c]]
            dp[i] %= MOD
        last[c] = i

print(dp[-1])

Submission status: Accepted

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

INF = 10 ** 9
MOD = 10 **9 + 7

N = int(input())

C = [int(input()) for _ in range(N)]
lst = [INF] * (2 * 10 ** 5 + 10) #各番号がどこにあるかを管理するリスト
ans = [1] * N
 
lst[C[-1]] = N - 1

for i in range(N - 2, -1, -1):
    c = C[i]
    if lst[c] == INF or lst[c] == i + 1:
        ans[i] = ans[i + 1]
    else:
        ans[i] = ans[i + 1] + ans[lst[c]]
    ans[i] %= MOD
    lst[c] = i

# print (ans)
print (ans[0] % MOD)

Submission status: Accepted

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

INF = 10 ** 9
MOD = 10 **9 + 7

N = int(input())

C = [int(input()) for _ in range(N)]
lst = [INF] * (2 * 10 ** 5 + 10) #各番号がどこにあるかを管理するリスト
ans = [1] * N
 
lst[C[-1]] = N - 1

for i in range(N - 2, -1, -1):
    c = C[i]
    if lst[c] == INF or lst[c] == i + 1:
        ans[i] = ans[i + 1]
    else:
        ans[i] = ans[i + 1] + ans[lst[c]]
    lst[c] = i

# print (ans)
print (ans[0] % MOD)

Submission status: Accepted

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])

if len(l)==1:
    print(1)
    exit()
    
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: Accepted

Solution code:
from bisect import bisect_left
p = 10**9+7
N = int(input())
C = [int(input()) for _ in range(N)]
A = [0 for _ in range(N)]
B = {i:[0,-1] for i in range(1,2*10**5+1)}
for i in range(N):
    c = C[i]
    if B[c][-1]==i-1:
        A[i] = 0
    else:
        A[i] = 1
    B[c].append(i)
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1,N):
    if A[i]==1:
        ind = bisect_left(B[C[i]],i)
        j = B[C[i]][ind-1]
        dp[i+1] = (dp[i]+dp[j+1])%p
    else:
        dp[i+1] = dp[i]
print(dp[N])

Submission status: Accepted

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

MOD = 10**9 + 7

dp = [0] * N
prev_i = [-1] * (2 * 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] % MOD)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = [I() for _ in range(n)]
    b = [a[0]] + [a[i] for i in range(1,n) if a[i] != a[i-1]]
    l = len(b)
    r = [0] * l
    r[0] = 1
    c = collections.defaultdict(int)
    c[b[0]] = 1
    for i in range(1,l):
        t = c[b[i]]
        t += r[i-1]
        t %= mod
        c[b[i]] = t
        r[i] = t

    return r[-1]


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

# 同色が直前に出現した位置を取っておく
prev = [INF] * N
D = {}
for i, a in enumerate(A):
    if a in D:
        prev[i] = D[a]
    D[a] = i

# dp[i] := 添字iが右端となる区間までの通り数
dp = [0] * N
dp[0] = 1
for i in range(1, N):
    # 1つ前と変化しない遷移は必ずある
    dp[i] += dp[i-1]
    # 左隣りが違う色でかつ、自分より左に同色があるなら、挟んで変色させる遷移をする
    if A[i-1] != A[i] and prev[i] != INF:
        # 挟む左端となる場所から遷移させる
        dp[i] += dp[prev[i]]
    dp[i] %= MOD
print(dp[N-1])

Submission status: Accepted

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(200001)]
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)
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: Accepted

Solution code:
MOD = 1000000007

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

prev = [None for _ in range(max(C)+1)]
dp = [0 for _ in range(N+1)]
dp[0] = 1

for i in range(N):
    if prev[C[i]] is None or prev[C[i]]==i:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i] + dp[prev[C[i]]]
    dp[i+1] %= MOD
    prev[C[i]] = i+1
    
print(dp[N])

Submission status: Accepted

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

def main():
    N = int(input())
    c = [-1]
    INF = 10**9+7
    for _ in range(N):
        a = int(input())
        if c[-1] == a-1:
            continue
        c.append(a-1)
    
    c.pop(0)
    d,M = len(c),max(c)
    dp = [1 for _ in range(d+1)]
    c_dp = [0 for _ in range(M+1)]
    for i in range(d):
        now = c[i]
        dp[i+1] = (dp[i] + c_dp[now])%INF
        c_dp[now] = dp[i+1]
                
    print(dp[-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(2 * pow(10, 5) + 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[4], table[3])
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  k = bl(table[a[i]], i)
  if j < len(table[a[i]]) and (table[a[i]][k] == 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: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7
data=[[] for i in range(max(C)+1)]
for i in range(N):
    data[C[i]].append(i)
dp=[0]*N
dp[0]=1
for i in range(1,N):
    h=data[C[i]]
    b=bisect_left(h,i)
    if b==0:
        dp[i]=dp[i-1]
    elif C[i]==C[i-1]:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[h[b-1]])%mod
print(dp[-1]%mod)

Submission status: Accepted

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


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

mod = 10**9+7

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

for i, a in enumerate(A):
    ind = last_ind[a]
    if ind == -1 or ind == i-1:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = (dp[i] + dp[ind+1] + 1) % mod
    last_ind[a] = i

print((dp[N]+1)%mod)

Submission status: Accepted

Solution code:
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(nn)]
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: Accepted

Solution code:
from collections import defaultdict

N = int(input())
C = [int(input())]
for _ in range(N - 1) :
  c = int(input())
  if c != C[-1] :
    C.append(c)

mod = 10 ** 9 + 7

ret = 1
dp = defaultdict(int)
for c in C :
  tmp = dp[c]
  dp[c] += ret
  ret += tmp
  dp[c] %= mod
  ret %= mod

print(ret)

Submission status: Accepted

Solution code:
def examB(mod):
    N = I(); C = [I() for _ in range(N)]
    dp = [0]*(N); dp[0] = 1
    cur = [0]*(max(C)+1); cur[C[0]] =1
    for i in range(1,N):
        if C[i]==C[i-1]:
            dp[i] = dp[i-1]
        else:
            dp[i] = cur[C[i]] + dp[i-1]
            dp[i] %=mod
            cur[C[i]] = dp[i]
#    print(dp)
    ans = dp[-1]%mod
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB(mod)

Submission status: Accepted

Solution code:
def main():
	n, *cs = map(int, open(0))
	fwd = [0] * n
	mod = 10 ** 9 + 7
	d = {}
	for i, c in enumerate(cs[::-1], start=1):
		f = d.get(c, 0)
		if f:
			fwd[n - i] = f
		d[c] = n - i
	dp = [0] * (n + 1)
	dp[0] = 1
	for i, fwd in enumerate(fwd, start=1):
		dp[i] += dp[i - 1] % mod
		if fwd > i:
			dp[fwd + 1] += dp[i] % mod
	print(dp[-1] % mod)

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
n, *cs = map(int, open(0))
fwd = [0] * n
mod = 10 ** 9 + 7
d = {}
for i, c in enumerate(cs[::-1], start=1):
	f = d.get(c, 0)
	if f:
		fwd[n - i] = f
	d[c] = n - i
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] += dp[i - 1]
	dp[i] %= mod
	# 隣だったら無視
	if fwd[i - 1] > i:
		dp[fwd[i - 1] + 1] += dp[i]
print(dp[-1])