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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = ILs(N)

dic = DD(list)
for i in range(N):
  dic[A[i]].append(i)
  
dp = [0 for i in range(N)]
dp[0] = 1
for i in range(N):
  c = A[i]
  p = bisect.bisect(dic[c],i)
  if p < len(dic[c]):
    if dic[c][p] != i+1:
      dp[dic[c][p]] += dp[i]
      dp[dic[c][p]]  %= MOD
  if i+1 < N:
    dp[i+1] += dp[i]
    dp[i+1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
s = set()
dic = {}
memo = [0]*(N+1)
sm = {}
memo[0] = 1
P = 10**9 + 7
b = 0

for i in range(1,N+1):
  c = int(input())
  if c not in s:
    s.add(c)
    dic[c] = [i]
    memo[i] = memo[i-1]
  else:
    memo[i] = memo[i-1]
    if b != c:
      if len(dic[c]) == 1:
        sm[c] = memo[dic[c][0]-1]
      else:
        sm[c] += memo[dic[c][-1]-1]
      memo[i] += sm[c]
      memo[i] %= P
      dic[c].append(i)
  b = c
      
print(memo[N])

Submission status: Accepted

Solution code:
import sys


input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	dd = dict()
	
	v = int(input())
	dd[v] = 0
	ll=[0]*n
	ll[0]=1
	for i in range(1, n):
		v = int(input())
		if v not in dd or dd[v] == i-1:
			ll[i] = ll[i-1]
			dd[v] = i
		else:
			ll[i] = (ll[i-1] + ll[dd[v]])%mod
			dd[v] = i
	return ll[-1]
			
		
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
c = [None]*n
for i in range(n):
    c[i] = int(input())
    
dp = [0]*(n+1)
dp[0] = 1
M = 10**9+7
# from collections import defaultdict
d = {}
for i,cc in enumerate(c):
    if cc not in d or d[cc]==i-1:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i] + dp[d[cc]+1]
    d[cc] = i
    dp[i+1] %= M
print(dp[n])

Submission status: Accepted

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

na = [a[0]]
for i in range(n-1):
    if a[i] != a[i+1]:
        na.append(a[i+1])
        
m = len(na)
cur = [-1]*(max(na)+1)

dp = [0]*(m+1)
dp[0] = 1
for i in range(m):
    if cur[na[i]] != -1:
        dp[i+1] = (dp[i] + dp[cur[na[i]]]) % MOD
        cur[na[i]] = i+1
    else:
        cur[na[i]] = i+1
        dp[i+1] = dp[i]
        
print(dp[m])

Submission status: Accepted

Solution code:
N = int(input())
L = [-1] * (2 * 10 ** 5 + 1)
mod = 10 ** 9 + 7

dp = [0] * (N + 1)

dp[0] = 1

for i in range(N):
    dp[i+1] += dp[i]
    color = int(input())
    if L[color] != -1 and L[color] != i:
        dp[i+1] += dp[L[color]]
    L[color] = i+1
    dp[i+1] %= mod

print(dp[N])

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import defaultdict

    n = int(readline())
    dp = [0] * (n + 1)
    dp[0] = 1
    memo = defaultdict(int)
    mod = 10 ** 9 + 7
    for i in range(1, n + 1):
        c = int(readline())
        dp[i] = dp[i - 1]
        if 0 < memo[c] < i - 1:
            dp[i] += dp[memo[c]]
        memo[c] = i
        dp[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    c = [int(input()) for i in range(n)]
    lac = [-1]* 200010
    dp = [0]*n

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

Submission status: Accepted

Solution code:
n = int(input())
iro = [-1 for i in range(2*(10**5)+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] != -1 and iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp[n])

Submission status: Accepted

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

for i,v in enumerate(c):
    if i > 0 and v == c[i-1]:
        continue
    v_c.append(v)

dp = [1]*(n+1)
color_cnt = [-1]*(2*10**5+5)
for i in range(1, len(v_c)+1):
    color = v_c[i-1]
    if color_cnt[color] > 0:
        dp[i] = dp[i-1] + dp[color_cnt[color]]
    else:
        dp[i] = dp[i-1]
    dp[i] %= MOD
    color_cnt[color] = i
print(dp[len(v_c)])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
c = [0] + list(map(int,read().split()))

mod = 10**9 + 7
m = 2*10**5

before = [-1] * (m+1)
dp = [0] * (n+1)
dp[0] = 1

for i,ci in enumerate(c[1:],1):
    if(c[i-1]==ci):
        dp[i] = dp[i-1]
        continue

    if(before[ci] == -1):
        dp[i] = dp[i-1]
        before[ci] = i
        continue

    dp[i] = (dp[i-1] + dp[before[ci]])%mod
    before[ci] = i

print(dp[-1])

Submission status: Accepted

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

dp = [0] * (N+1)
dp[0] = 1
last_idx = {}
for i, c in enumerate(C, 1):
  dp[i] = dp[i-1]
  if c in last_idx:
    idx = last_idx[c]
    if idx != i - 1:
      dp[i] += dp[idx]
      dp[i] %= MOD
  last_idx[c] = i

print(dp[-1]%MOD)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#import numpy as np

def main():
	n=II()
	C=[]
	pre=0
	for i in range(n):
		a=II()
		if a!=pre:
			C.append(a)
		pre=a
	#print(C)

	n=len(C)
	dp=[0]*(n+1)
	dp[1]=1
	li=[0]*(max(C)+10)
	li[C[0]]=1

	for i in range(1,n):
		#print(dp)
		#print(li)
		dp[i+1]=(dp[i]+dp[li[C[i]]])%(10**9+7)
		li[C[i]]=i+1
	print(dp[-1])


if __name__ == "__main__":
	main()

Submission status: Accepted

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

count = [0]*(200005)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9+7
#dp[i]: i番目までの場合の数
for i in range(n):
    dp[i+1] = dp[i]
    if c[i+1] != c[i]:
        dp[i+1] += count[c[i+1]]
        dp[i+1] %= mod
        count[c[i+1]] += dp[i]
        count[c[i+1]] %= mod

print(dp[n]%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n = int(input())
c = [int(input()) for _ in range(n)]
import copy
cc = copy.deepcopy(c)
color_sum = {i: 0 for i in range(10 ** 6)}
dp = [1 for _ in range(n + 1)]
color_sum[cc[0]] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    if cc[i - 2] == cc[i - 1]:
        continue
    dp[i] += color_sum[cc[i - 1]]
    dp[i] %= mod
    color_sum[c[i - 1]] += dp[i - 1]
    color_sum[c[i - 1]] %= mod
print(dp[n])

Submission status: Accepted

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

color_sum = {i: 0 for i in range(10 ** 6)}
dp = [1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
color_sum[c[0]] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1]

    if c[i-2] == c[i-1]:
        continue

    dp[i] += color_sum[c[i-1]]
    dp[i] %= mod

    color_sum[c[i-1]] += dp[i-1]
    color_sum[c[i-1]] %= mod


print(dp[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
C=[]
MAX=-1
for i in range(N):
    c=int1(input())
    MAX=max(MAX,c)
    if not C or (C and C[-1]!=c):
        C.append(c)
M=len(C)
dp=[0]*(M+1)
dp[0]=1
last=[-1]*(MAX+1)
for i in range(M):
    if last[C[i]]!=-1:
        dp[i+1]+=dp[i]+dp[last[C[i]]]
    else:
        dp[i+1]=dp[i]
    dp[i+1]%=MOD
    last[C[i]]=i+1
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()

dp = [1,1]
last_idx = [-1]*(2*10**5 + 1)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

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

dp = [1,1]
last_idx = [-1]*(N+10)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [-1]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * N
    dp[0] = 1
    used = [-1] * (max(C) + 1)
    used[C[0]] = 0

    for i in range(1, N):
        if used[C[i]] == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[used[C[i]]]

        dp[i] %= MOD
        used[C[i]] = i

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    stone_last_pos=[-1]*(2*10**5+1)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        c=int(input())
        place=stone_last_pos[c]
        if place==i-1 or place==-1:
            dp[i]=dp[i-1]
        else:
            dp[i]=(dp[i-1]+dp[place])%mod
        stone_last_pos[c]=i
    print(dp[n])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    stone=[0]*(2*10**5+1)
    stone_last_pos=[-1]*(2*10**5+1)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        c=int(input())
        place=stone_last_pos[c]
        if place==i-1 or place==-1:
            dp[i]=dp[i-1]
        else:
            dp[i]=(dp[i-1]+dp[place])%mod
        stone_last_pos[c]=i
    print(dp[n])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    CMAX = 2*10**5
    A = [0 for _ in range(CMAX+1)]
    S = [1 for _ in range(CMAX+1)]
    C = [NI() for _ in range(N)]
    P = 1
    A[C[0]] = 1
    for i in range(1,N):
        if C[i] != C[i-1] and A[C[i]] > 0:
            S[C[i]] = S[C[i]] + P
        else:
            S[C[i]] = P
        A[C[i]] = 1
        P = S[C[i]] % MOD
    print(P)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
c=[int(input()) for _ in range(n)]
color_sum=[0]*200001
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
color_sum[c[0]]+=1
# i個目まで考えたときの解。求めるのはdp[n]
# dp[i]:i個目より前で、i個目と同じ色の石があるところをjとして、dp[j-1]の和+dp[i-1]
for i in range(1,n): #二個目からn-1個目の計算をする。
  dp[i+1]=dp[i]
  if c[i]==c[i-1]:
    continue
  dp[i+1]+=color_sum[c[i]]
  color_sum[c[i]]=dp[i+1]
print(dp[n]%(pow(10,9)+7))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0]*(N+1)
lis = [-1] * (2 * 10**5 + 1)
dp[0] = 1
lis[C[0]] = 0
for i,c in enumerate(C[1:],1):
    prev_i = lis[c]
    dp[i] = dp[i-1]
    if prev_i != i-1:
        dp[i] += dp[prev_i]
        dp[i] %= MOD
    lis[c] = i
answer = dp[N-1]
print(answer)

Submission status: Accepted

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

mod = 10**9+7
newC = [C[0]]
for c in C:
    if newC[-1] == c:
        continue
    newC.append(c)

N = len(newC)
L = [0]*(N+1)
L[0] = 1
idx = [-1]*(max(newC)+1)
for i in range(N):
    if idx[newC[i]] >= 0:
        L[i+1] += L[idx[newC[i]]]
        
    L[i+1] += L[i]
    L[i+1] %= mod
    idx[newC[i]] = i+1

print(L[-1])

Submission status: Accepted

Solution code:
n = int(input())

cl = []

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


ans = [1 for i in range(n)]

mod = 10**9+7

stones = dict()

stones[cl[-1]] = n-1

for i in range(n-1):
    cur = cl[n-i-2]

    if cur in stones and stones[cur] != n-i-1:
        ans[n-i-2] = ans[n-i-1] + ans[stones[cur]]
        ans[n-i-2] %= mod
    else:
        ans[n-i-2] = ans[n-i-1] % mod
    stones[cur] = n-i-2

print(ans[0])

Submission status: Accepted

Solution code:
n = int(input())
c = [int(input()) for _i in range(n)]
c.append(-1)
dic = [-1 for _i in range(10**5 *2 +1)]
dp = [0 for _i in range(n+1)]
dp[n] = 1
mod = 10**9 +7
for i in range(n):
    if c[i-1] != c[i]:
        if dic[c[i]] > 0:
            dp[i] = (dp[i-1] + dic[c[i]])%mod
        else:
            dp[i] = dp[i-1]
        dic[c[i]] = dp[i]
    else:
        dp[i] = dp[i-1]
    
print(dp[n-1]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from operator import itemgetter
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7


d = defaultdict(list)

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

pairs = []
for c, indices in d.items():
    for i in range(len(indices) - 1):
        if indices[i+1] - indices[i] > 1:
            pairs.append((indices[i], indices[i+1]))

pairs.sort(key = itemgetter(1))   


dp = np.zeros(N, np.int64)
dp[0] = 1
index = 0
for i in range(1, N):
    dp[i] = dp[i-1]
    while index < len(pairs) and pairs[index][1] == i:
        dp[i] += dp[pairs[index][0]] 
        index += 1
    dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=[]
    cnt=[0]*200005
    for _ in range(n):
        c=II()
        if not aa or aa[-1]!=c:aa.append(c)
    #print(aa)
    md=10**9+7
    ans=1
    for a in aa:
        cnt[a]=(cnt[a]+ans)%md
        ans=cnt[a]
    print(ans)

main()

Submission status: Accepted

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 = [[-1,-1]]
    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 = sorted(selist,key=lambda x:x[1])
    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]
        dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

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 = []
    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]
        dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

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 = []
    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)%mod
        ind = bisect_right(ends,selist[i][0])
        dp[i] += dp[ind-1]
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

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 = []
    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: Accepted

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

cc = []
prev = 0
for e in c:
    if e != prev:
        cc.append(e)
        prev = e

ln = len(cc)

dp_prev = 1
acc = [0] * (MAX + 1)

for i, e in enumerate(cc, 1):
    dp_now = dp_prev + acc[e]
    dp_now %= mod

    acc[e] += dp_prev
    acc[e] %= mod

    dp_prev = dp_now

print(dp_now)

Submission status: Accepted

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

cc = []
prev = 0
for e in c:
    if e != prev:
        cc.append(e)
        prev = e

ln = len(cc)

dp = [0] * (ln + 1)
dp[0] = 1
acc = [0] * (MAX + 1)

for i, e in enumerate(cc, 1):
    dp[i] = dp[i-1] + acc[e]
    dp[i] %= mod

    acc[e] += dp[i-1]
    acc[e] %= mod

print(dp[ln])

Submission status: Accepted

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

Solution code:
from collections import defaultdict
MOD = 10**9+7
n = int(input())
dp = [1]
d = defaultdict(list)
cur = int(input())
d[cur].append(0)
for i in range(1,n):
  pre,cur = cur,int(input())
  c = dp[-1]
  if pre != cur and d[cur]:
    c += dp[d[cur][-1]]
  dp.append(c%MOD)
  d[cur].append(i)
print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9+7
n = int(input())
dp = [1]
d = defaultdict(list)
cur = int(input())
d[cur].append(0)
for i in range(1,n):
  pre,cur = cur,int(input())
  c = dp[-1]
  if pre != cur and d[cur]:
    c += dp[d[cur][-1]]
  dp.append(c)
  d[cur].append(i)
print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = pow(10,9)+7
N = int(input())
C = [int(input()) for i in range(N)]

DP = [1]*N
counter = Counter()
for i in range(N):
    c = C[i]
    if i==0:
        counter[c]+=1
    elif i==1:
        if c!=C[i-1]:
            counter[c]+=1
    else:
        DP[i] = DP[i-1]
        if c!=C[i-1]:
            DP[i]+=counter[c]
            counter[c]+=DP[i-1]
print(DP[N-1]%MOD)

Submission status: Accepted

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

dp = [0] * (n + 1)
dp[0] = 1
prev = [-1] * (10 ** 6)
for i, x in enumerate(c):
    dp[i + 1] = dp[i]
    if 0 <= prev[x] < i:
        dp[i + 1] += dp[prev[x]]
        dp[i + 1] %= MOD
    prev[x] = i + 1
print(dp[n])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(2*10**5)
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: Accepted

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

def main():
  MAX = 10**9 + 7
  
  n = int(input())
  lc = [int(input()) for _ in range(n)]
  dp = [0] * (n)
  
  last_is = [-1]*(2*10**5+1)
  dp[0] = 1
  last_is[lc[0]] = 0
  for i,c in enumerate(lc[1:], 1):
    last_i = last_is[c]
    dp[i] = dp[i-1]
    if last_i != -1 and last_i != i-1:
      dp[i] += dp[last_i]
      dp[i] %= MAX
    last_is[c] = i

  print(dp[-1])
  

if __name__=='__main__':
  main()

Submission status: Accepted

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]*(max(A)+1)
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: Accepted

Solution code:
# dp[i]
# ある石が初めて出てくるときは、場合の数は増えない
# 1 2  -> ここまでは1通り
# 1 2 3 -> 3が初めて出てきたので、1通りのまま
# 1 2 3 2 -> 2は二度目に出てきたので1,2,3までの場合の数1と、2が最後に出た場合の数1を足す
# dpは[1,1,1,2]となる
# 1 2 3 2 2 -> 前回と同じ文字が出てきたときはパターンが増えない（そこで切れない）
# dpは[1,1,1,2,2]
# 1 2 3 2 2 3 -> 3は二度目に出てきたので、1,2,3,2,2までの場合の数2と、3が最後に出た場合の数1を足す
# dpは[1,1,1,2,2,3]
# dpの他に、「ある数が最後に出てきたときのindex」を管理する

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

DIV = 10 ** 9 + 7

dp = [0 for i in range(N)]
dp[0] = 1
index = [-1] * (max(C)+1) # ある数が最後に出てきたindex
index[C[0]] = 0 # ループを1から回すので、最初の数だけ「最後に登場したindexは0」を代入

for i in range(1,len(C)):
  if C[i] == C[i-1]:
    dp[i] = dp[i-1] # 直前と同じ文字のときはパターンが増えない
  elif index[C[i]] == -1:
    # 初めて出てきた文字のときは場合の数が増えない
    dp[i] = dp[i-1]
  else:
    # 二回目以降に出てきた場合、場合の数を足す
    dp[i] = ( dp[i-1] + dp[index[C[i]]] ) % DIV
  # 最後に出てきたindexを更新する
  index[C[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
c = [int(input()) for _ in range(n)]
l = [c[0]]
for i in range(1, n):
    if c[i] != c[i - 1]:
        l.append(c[i])
n = len(l)
p = [-1] * (max(c) + 1)
q = [-1] * n
for i, x in enumerate(l[::-1]):
    q[n - i - 1] = p[x]
    p[x] = n - i - 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
    dp[i + 1] += dp[i]
    if q[i] != -1:
        dp[q[i] + 1] += dp[i + 1]
print(dp[n] % MOD)

Submission status: Accepted

Solution code:
INF = 10 ** 9
MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  copy import deepcopy
from bisect import bisect_left

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

    dic = {i:0 for i in set(C)}
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(n):
        if i > 0 and C[i] == C[i - 1]:
            dp[i + 1] = dp[i]
            continue
        else:
            dp[i + 1] = (dp[i] + dic[C[i]])%MOD
            dic[C[i]] += dp[i]
            dic[C[i]] %= MOD
    print(dp[-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
C = [INT() for _ in range(N)]
dp = [0]*(N+1)
dp[0] = 1
dp2 = [-1]*(max(C)+1)  # 前に色iが出てきたインデックスを保存
for i in range(1, N+1):
	p = dp2[C[i-1]]  # 色C[i-1]が前に出てきたインデックス
	if i-p > 1 and p != -1:  # インデックスがあり，前の要素でない
		dp[i] += dp[p]
	dp2[C[i-1]] = i
	dp[i] += dp[i-1]
	dp[i] %= mod

print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
dp=[1 for i in range(0,N)]
data={i:-1 for i in range(1,2*10**5+1)}
mod=10**9+7

c=int(input())
data[c]=0

for i in range(1,N):
    c=int(input())
    if data[c]==i-1:
        dp[i]=dp[i-1]
    elif data[c]==-1:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[data[c]])%mod
    data[c]=i

print(dp[N-1])