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

Solution (Python):

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








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



if __name__ == '__main__':
    solve()

Solution (Python):
import bisect

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

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


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

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[-1]%MOD)

Solution (Python):
import bisect

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

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


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

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)


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(dp[-1]%MOD)

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

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


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

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)


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[-1]%MOD)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
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()

Solution (Python):


N=int(input())

l=[0]*2*10**5
k=[0]*2*10**5

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

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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=[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])

Solution (Python):
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]
    
    
print(x[n-1])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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


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と同じ色が出てきたところの手前のとりうる列の数だけ新たに列を作ることができるため）
        を繰り返せば、最終的な数が求まる

        """
        
        if c in last and last[c] < i-1:
            dp[i] += dp[last[c]]
            dp[i] %= MOD
        last[c] = i

print(dp[-1])

Solution (Python):
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[0] % MOD)

Solution (Python):
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[0] % MOD)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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(dp[-1] % MOD)

Solution (Python):
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())

Solution (Python):


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 = [0] * N
dp[0] = 1
for i in range(1, N):
    
    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])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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


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

Solution (Python):
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)

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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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]

    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)

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

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

show_flg=False
show_flg=True

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

print(dp[-1]%mo)

Solution (Python):

import sys
from collections import defaultdict

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  

MOD = 10 ** 9 + 7
d = dict()

N = ni()
C = [ni() for _ in range(N)]
dp = [1] * N
d[C[0]] = 0

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

print(dp[N-1])

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
mod = 10**9+7

N = int(input())
dp = [0] * (N+1)
dp[0] = 1
prev = defaultdict(lambda: -1)
for i in range(1, N+1):
    c = int(input())
    dp[i] = dp[i-1]
    if prev[c] >= 0:
        if prev[c] != i-1:
            dp[i] = (dp[i] + dp[prev[c]]) % mod
    prev[c] = i

print(dp[-1])