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):
def main():
    n = int(input())
    c = []
    mod = 10 ** 9 + 7
    state = [0 for i in range(n+200000)]
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(n):
        c_i = int(input())

        if state[c_i] >= 1 and state[c_i] != i:
            dp[i+1] = (dp[state[c_i]] + dp[i]) % mod
        else:
            dp[i+1] = dp[i] % mod

        state[c_i] = i + 1
    print(dp[-1] % mod)

main()

Solution (Python):
n=int(input())
c=list(int(input()) for i in range(n))
dp=[0]*n
rec=[0]*(2*10**5+1)
dp[0]=1
rec[c[0]]=1
for i in range(1,n):
	if c[i]==c[i-1]:
		dp[i]=dp[i-1]
		continue
	dp[i]=(dp[i-1]+rec[c[i]])%(10**9+7)
	rec[c[i]]=dp[i]
print(dp[-1])

Solution (Python):

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


k = [0 for _ in range((2 * 10**5) + 1)]


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


print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, C):
    C_ = [-1]
    for c in C:
        if C_[-1] == c:
            continue
        C_.append(c)
    
    C = C_

    mod = 10**9 + 7
    S = defaultdict(lambda: 0)
    ans = 1
    for c in C:
        ans = (ans + S[c]) % mod
        S[c] = ans

    return ans


def main():
    N = read_int()
    C = [read_int() for _ in range(N)]
    print(slv(N, C))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

MOD = 10 ** 9 + 7

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

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



d = defaultdict(lambda: -1)




for i, cc in enumerate(c, 1):
    dp[i] = dp[i - 1]
    
    
    
    if 1 <= d[cc] < i - 1:
        
        
        dp[i] += dp[d[cc]]
        
        
    dp[i] %= MOD
    d[cc] = i
    
    
print(dp[N])

Solution (Python):
N=int(input())
lst=[0]
mod=10**9+7
for i in range(N):
  a=int(input())
  if lst[-1]==a:
    continue
  else:
    lst.append(a)
length=len(lst)
L=[0]*(2*10**5+1);DP=[0]*(length-1)
DP.insert(0,1)
for i in range(1,length):
  if L[lst[i]]==0:
    DP[i]=DP[i-1]%mod
    L[lst[i]]=i
  else:
    j=L[lst[i]]
    DP[i]=(DP[i-1]+DP[j])%mod
    L[lst[i]]=i
print(DP[-1])

Solution (Python):

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

dic = dict()
dp = [None] * N
for i, x in enumerate(C):
    if x in dic:
        dp[i] = dic[x]
    dic[x] = i

dp2 = [0] * N
dp2[0] = 1
for i in range(1, N):
    dp2[i] = dp2[i - 1]
    if dp[i] is not None and i - 1 != dp[i]:
        dp2[i] = (dp2[i] + dp2[dp[i]]) % MOD

print(dp2[-1])

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
c2 = [int(input()) for _ in range(N)]
mod = 10**9+7

c = [c2[0]-1]
n = N
for i in range(1,N):
    if c2[i] == c2[i-1]:
        n -= 1
        continue
    c.append(c2[i]-1)



used = [-1]*(max(c)+1)
used[c[0]] = 0

dp = [0]*n
dp[0] = 1
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]]])%mod
    used[c[i]] = i

print(dp[-1])

Solution (Python):
import sys


def tran(A):
    temp = []
    for i in range(len(A)):
        if i == 0:
            temp += [A[i]]
        elif A[i] != A[i - 1]:
            temp += [A[i]]
    return temp


def find(A):
    
    dp = [1] * len(A) + [1]

    current_dic = {}

    MOD = 10**9 + 7

    for i in range(len(A)):

        if i == 0:
            current_dic[A[i]] = 1
        else:
            temp = dp[i - 1]
            if A[i] in current_dic:
                temp += current_dic[A[i]]
                temp %= MOD
                current_dic[A[i]] += dp[i - 1]
                current_dic[A[i]] %= MOD
            else:
                current_dic[A[i]] = dp[i - 1]

            dp[i] = temp
    
    return dp[-2] % MOD


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



print(find(tran(A)))

Solution (Python):
n = int(input())
C = [0] + [int(input()) for i in range(n)]
p = 10 ** 9 + 7

DP = [0] * (n + 1)
last = [0] * int(2e5 + 1)
DP[0] = 1

for i in range(n):
    if C[i + 1] == C[i]:
        DP[i + 1] = DP[i] % p
    else:
        DP[i + 1] = (DP[i] + last[C[i + 1]]) % p
    last[C[i + 1]] = DP[i + 1]

print(DP[n])

Solution (Python):
N = int(input())
C = [int(input()) for _ in range(N)]
C = [x for x,y in zip(C[:-1],C[1:]) if x!=y] + [C[-1]]

DP = [1]
dic = {}

for i in range(len(C)):   
    DP.append((DP[-1]+dic.get(C[i],0))%(10**9+7))    
    dic[C[i]] = DP[-1]
print(DP[-1])

Solution (Python):
N = int(input())
C = [int(input()) for _ in range(N)]
C = [x for (x,y) in zip(C[:-1], C[1:]) if x!=y] + [C[-1]]

SUM = 1
DP_dict = {}

for c in C:
  if c in DP_dict.keys():
    SUM += DP_dict[c]
  DP_dict[c] = SUM

print(SUM % (10**9+7))

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

SUM = 1
DP_dict = {}

for c in C:
  if c not in DP_dict.keys():
    DP_dict[c] = SUM
  else:
    SUM += DP_dict[c]
    DP_dict[c] = SUM

print(SUM % (10**9+7))

Solution (Python):
from collections import defaultdict
 
mod = 10 ** 9 + 7
n = int(input())
C = [int(input()) for i in range(n)]
 
for i in range(n - 1, 0, -1):
    if C[i] == C[i - 1]:
        del C[i]
        
        
D = defaultdict(int)
ans = 1
for c in C:
    ans += D[c]
    D[c] = ans
    

print(ans % mod)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
c2 = [int(input()) for _ in range(N)]
mod = 10**9+7

c = [c2[0]-1]
n = N
for i in range(1,N):
    if c2[i] == c2[i-1]:
        n -= 1
        continue
    c.append(c2[i]-1)



used = [-1]*(max(c)+1)
used[c[0]] = 0

dp = [0]*n
dp[0] = 1
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]]])%mod
    used[c[i]] = i

print(dp[-1])

Solution (Python):
n = int(input())
C = []
MOD = 10 ** 9 + 7
pre = -1
for i in range(n):
    a = int(input())
    if a != pre:
        C.append(a)
    pre = a

N = len(C)
dp = [0] * (N + 1)
col = {}
pre = -1
dp[0] = 1
for i in range(1, N + 1):
    if C[i - 1] not in col:
        dp[i] = dp[i - 1]
        col[C[i - 1]] = dp[i]
    else:
        dp[i] = dp[i - 1]
        dp[i] += col[C[i - 1]]
        dp[i] %= MOD
        col[C[i - 1]] += dp[i - 1]

print(dp[N])

Solution (Python):
from collections import defaultdict as dd
d = dd(int)
r = 1
p = ""
for _ in range(int(input())):
  c = input()
  if c != p:
    r = (r + d[c]) % (10**9 + 7)
    d[c] = r
  p = c
print(r)

Solution (Python):

import sys

MOD = 1000000007  

memory = {}


def solve(N: int, C: "List[int]"):
    

    dp = [0]*N
    last = [-1]*(2*(10**5)+1)
    for i, s in enumerate(C):
        if i == 0:
            dp[i] = 1
        else:
            dp[i] = dp[i-1]
            if last[s] != -1 and last[s] < i-1:
                dp[i] = (dp[i] + dp[last[s]]) % MOD
        last[s] = i
    
    print(dp[-1])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    C = [int(next(tokens)) for _ in range(N)]  
    solve(N, C)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
mod = 10**9 + 7
N = int(input())
C = [int(input()) for i in range(N)]
dq = deque()
dq.append(C[0])
for c in C:
    if c != dq[-1]:
        dq.append(c)
C = list(dq)
N = len(C)
dp = [0]*(N+1)
dp[0] = 1
acc = [0]*(2*pow(10,5)+1)
for i in range(1,N+1):
    dp[i] = dp[i-1]
    dp[i] += acc[C[i-1]]
    dp[i] %= mod
    acc[C[i-1]] += dp[i-1]
    acc[C[i-1]] %= mod
ans = dp[N]
print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
stones = []
last = None
n_stone = 0
for i in range(N):
    stone = int(input())
    if stone != last:
        stones.append(stone)
        last = stone

count = defaultdict(int)
seq = 1
for i, c in enumerate(stones):
      prev = count[c]
      count[c] = prev + seq
      seq += prev

print(seq % (10**9 + 7))

Solution (Python):


import sys
from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


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

    dp = [0] * (n + 1)
    dp[0] = 1
    color_index = defaultdict(int)
    for i, c in enumerate(C):
        if not color_index[c]:
            color_index[c] = i + 1
            dp[i + 1] = dp[i]
        else:
            if color_index[c] == i:
                dp[i + 1] = dp[i]
            else:
                dp[i + 1] = dp[i] + dp[color_index[c]]
                dp[i + 1] %= MOD
            color_index[c] = i + 1

    return dp[-1]


print(main())

Solution (Python):
from collections import defaultdict

MOD = 10 ** 9 + 7

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

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

d = defaultdict(lambda: -1)

for i, cc in enumerate(c, 1):
    dp[i] = dp[i - 1]
    if 0 <= d[cc] < i - 1:
        dp[i] += dp[d[cc]]
    dp[i] %= MOD
    d[cc] = i
    
    
print(dp[N])

Solution (Python):
from collections import defaultdict

MOD = 10 ** 9 + 7

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

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

d = defaultdict(lambda: -1)

for i, cc in enumerate(c, 1):
    if c[i - 1] == c[i - 2]:
        dp[i] = dp[i - 1]
    elif d[cc] == -1:
        
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[d[cc]]
    dp[i] %= MOD
    d[cc] = i
    
    
print(dp[N])

Solution (Python):
import sys

N = int(input())
C = [int(sys.stdin.readline()) for _ in range(N)]
MOD = 10**9 + 7
A = []
for c in C:
    if A and A[-1] == c:
        continue
    A.append(c)
NA = len(A)
last = [-1] * 200001
B = [-1] * 200001
for i, a in enumerate(A):
    B[i] = last[a]
    last[a] = i

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

Solution (Python):

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


def A():
    n = I()
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    ans = 1
    for i in d.keys():
        ans *= d[i]+1
        ans %= mod
    print(ans-1)

def B():
    n = I()
    c = IR(n)
    v = [[i+1] for i in range(n-1)]
    v.append([])
    d = defaultdict(deque)
    for i in range(n):
        d[c[i]].append(i)
    for i in d.keys():
        x = None
        while d[i]:
            y = d[i].popleft()
            if x != None and y != x+1:
                v[x].append(y)
            x = y
    path = [0]*(n)
    path[0] = 1
    q = [0]
    for x in range(n-1):
        for y in v[x]:
            path[y] += path[x]
            path[y] %= mod
    print(path[-1])

def C():
    sys.setrecursionlimit(100000)
    n,a,b = LI()
    def dfs(l,q,f):
        if len(l) == po2[n]:
            if l[-1] == b:
                print("YES")
                print(*l)
                quit()
        x = l[-1]
        m = -1
        k = -1
        for i in po2[:-1]:
            y = x^i
            if f[y] > m:
                m = f[y]
                k = y
        if m != -1:
            for i in po2[:-1]:
                y = x^i
                if f[y] == m:
                    q.append(y)
            for y in q:
                dfs(l+[y],[],f[:y]+[-1]+f[y+1:])
    po2 = [1]*(n+1)
    for i in range(1,n+1):
        po2[i] = po2[i-1]*2
    ans = [a]
    f = [0]*po2[n]
    for i in range(po2[n]):
        k = b^i
        c = 0
        while k > 0:
            c += k%2
            k//= 2
        f[i] = c
    if not f[a] in [1,3,5,7,9,11,13,15,17,19]:
        print("NO")
        quit()
    f[a] = -1
    l = [a]
    dfs(l,[],f)
    print("NO")

def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    B()

Solution (Python):
n = int(input())
cc = [int(input()) for i in range(n)]
c = [cc[0]]
for i in range(1,n):
  if cc[i] != cc[i-1]:
    c.append(cc[i])

n = len(c)
dp = [0 for i in range(n)]
pos_dp = [-1 for i in range(2*10**5+1)]

dp[0] = 1
pos_dp[c[0]] = 0
     
for i in range(1,n):
  if pos_dp[c[i]]!=-1:
    dp[i] = (dp[i-1] + dp[pos_dp[c[i]]])%1000000007
  else:
    dp[i] = dp[i-1] 
  pos_dp[c[i]] = i

print(dp[n-1])

Solution (Python):
n,*c=map(int,open(0).readlines())
l=[-1]*2**18
b=[]
for i in range(n):
  b.append(l[c[i]])
  l[c[i]]=i
dp=[1]+[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]
  if c[i]!=c[i-1]and b[i]>-1:
    dp[i]=(dp[i]+dp[b[i]])%(10**9+7)
print(dp[-2])

Solution (Python):
n,*c=map(int,open(0).readlines())
l=[-1]*2**18
b=[]
for i in range(n):
  b.append(l[c[i]])
  l[c[i]]=i
dp=[1]+[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]
  if c[i]!=c[i-1]and b[i]>-1:
    dp[i]=(dp[i]+dp[b[i]])%(10**9+7)
print(dp[-2])

Solution (Python):
import sys
from collections import defaultdict

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

ans = 1
dic = defaultdict(lambda: 0)
mod = 10 ** 9 + 7
for c in C:
    a = dic[c]
    dic[c] += ans
    ans = (ans + a) % mod

print(ans % mod)

Solution (Python):
N=int(input())
C=[int(input())-1 for i in range(N)]
mod=10**9+7
pre_dp=[0]*(max(C)+1)
dp=[0]*(N+1)
dp[0]=1
dp[1]=1
pre_dp[C[0]]=1
for i in range(1,N):
  if C[i]!=C[i-1]:
    dp[i+1]=(dp[i]+pre_dp[C[i]])%mod
    pre_dp[C[i]]=(pre_dp[C[i]]+dp[i])%mod
  else:
    dp[i+1]=dp[i]
    
print(dp[N])

Solution (Python):
import sys
from collections import defaultdict

N = int(input())
C = [0]
for _ in range(N):
    c = int(sys.stdin.readline())
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = defaultdict(lambda: 0)
mod = 10 ** 9 + 7
for c in C:
    a = dic[c]
    dic[c] += ans
    ans = (ans + a) % mod

print(ans % mod)

Solution (Python):
from collections import defaultdict
N = int(input())
C = [int(input()) for _ in range(N)]
dic = defaultdict(list)
for i in range(N):
    dic[C[i]].append(i)
es = [[] for _ in range(N)]
for i in range(N - 1):
    es[i].append(i + 1)
for key in dic:
    if len(dic[key]) == 1:
        continue
    i, L, v1, v2 = 1, len(dic[key]) - 1, dic[key][0], dic[key][1]
    while True:
        if v1 + 1 != v2:
            es[v1].append(v2)
        v1 = v2
        if i < L:
            i += 1
            v2 = dic[key][i]
        else:
            break
dp = [0 for _ in range(N)]
dp[0], MOD = 1, 10**9 + 7
for i in range(N - 1):
    for j in es[i]:
        dp[j] = (dp[j] + dp[i]) % MOD
print(dp[N - 1])

Solution (Python):
import sys
from collections import defaultdict

N = int(input())
C = [0]
for _ in range(N):
    c = int(sys.stdin.readline())
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = defaultdict(lambda: 0)
for c in C:
    a = dic[c]
    dic[c] += ans
    ans += a

print(ans % (10 ** 9 + 7))

Solution (Python):
from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(lambda: -1)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
for i in range(1, N + 1):
  C[i] = int(input())
  DP[i][0] = sum(DP[i - 1]) % p
  if C[i] != C[i - 1]:
    DP[i][1] = sum(DP[D[C[i]]]) if D[C[i]] != -1 else 0
    D[C[i]] = i
print(sum(DP[N]) % p)

Solution (Python):
import sys

N = int(input())
C = [0]
for line in sys.stdin:
    c = int(line)
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))

Solution (Python):
import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))

Solution (Python):
mod=7+10**9
n=int(input())
c=['$']+[int(input()) for _ in [0]*n]
data=[1]+[0]*n
s={}

for i in range(1,n+1):
  if c[i] in s.keys():
    if c[i]!=c[i-1]:
      s[c[i]]+=data[i-1]
      s[c[i]]%=mod
  else:
    s[c[i]]=data[i-1]
  data[i]=s[c[i]]%mod
        
print(data[n])

Solution (Python):
n = int(input())
l = [0 for i in range(2*(10**5)+1)]
a = [1]
co = 0
for i in range(n):
    k = int(input())
    b = a[-1]
    if l[k] != i and l[k] != 0:
        b += a[l[k]]
    l[k] = i+1
    a.append(b%(10**9+7))
print(a[-1])

Solution (Python):

from __future__ import division, print_function

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

range = xrange

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

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

MAGIC = 6755399441055744.0
SHRT = 65536.0

MODF_INV = 1.0 / MODF
SHRT_INV = 1.0 / SHRT

fround = lambda x: (x + MAGIC) - MAGIC
fmod = lambda a: a - MODF * fround(MODF_INV * a)


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

    c = [x[0] for x in itertools.groupby(c)]
    n = len(c)

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

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


if __name__ == '__main__':
    main()

Solution (Python):



N = int(input())
C = []

prev = -1

for _ in range(N):
    tmp = int(input())
    if tmp != prev:
        C.append(tmp)
    prev = tmp

dp = [0]*(len(C)+1)
place = {}
dp[0] = 1

for i in range(len(C)):
    if place.get(C[i]) != None:
        dp[i+1] = dp[i] + dp[place.get(C[i])]
    else:
        dp[i+1] = dp[i]
    place[C[i]] = i+1
    
print(dp[-1]%(10**9+7))

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

MOD = 1e9 + 7

C2 = []
re = ""
L = {}
LL = [-1] * N
for i in C:
  if i != re:
    if i in L:
      LL[L[i]] = len(C2)
      L[i] = len(C2)
    else:
      L[i] = len(C2)
    C2.append(i)
  re = i


DP = [-1] * (len(C2) + 1)

DP[-1] = 1
for i in range(len(C2) - 1, -1, -1):
  DP[i] = DP[i + 1]
  if LL[i] != -1:
    DP[i] += DP[LL[i]] % MOD
print(int(DP[0] % MOD))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    C = []
    for _ in range(N):
        c = II()
        if len(C) == 0 or c != C[-1]:
            C.append(c)
    global ans
    ans = 0
    dp = [1] + [0] * N
    from collections import defaultdict
    cnt_clr = defaultdict(int)
    for i, c in enumerate(C):
        ret = dp[i]
        ret += cnt_clr[c]
        cnt_clr[c] = ret
        dp[i + 1] = ret % MOD

    ans = dp[len(C)]

    return ans % MOD

print(main())

Solution (Python):

from bisect import bisect, bisect_left
from collections import defaultdict

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

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

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

Solution (Python):
from collections import defaultdict

d = defaultdict(int)
D = defaultdict(lambda:1)
N = int(input())

ans = 1
C = int(input())
d[C] += 1
c = C

for i in range(N - 1):
	C = int(input())
	d[C] += 1
	if C == c:
		pass
	else:
		if d[C] >= 2:
			ans = (ans + D[C]) % 1000000007
	D[C] = ans
	c = C

print(ans)

Solution (Python):

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
n=int(input())
C=[int(input()) for _ in range(n)]
A=[0]*(2*10**5+1) 
B=[1]
for i,c in enumerate(C):
    
    tmp=B[-1]
    if A[c]!=i and A[c]!=0:
        tmp+=B[A[c]]
    A[c]=i+1
    B.append(tmp%mod)

print(B[-1])

Solution (Python):
a = int(input())
C = list()
last = [-1] * 2 * 100002
for i in range(a):
    C.append(int(input()))

ans = [1] * a
last[C[0]] = 0

for i in range(1, a):
    ans[i] = ans[i - 1]
    if C[i] == C[i - 1]:
        continue
    if last[C[i]] != -1:
        ans[i] += ans[last[C[i]]]
    last[C[i]] = i

print(ans[a - 1] % 1000000007)

Solution (Python):
from collections import defaultdict


def search(colors):
    dp = [1] * len(colors)
    c_dict = defaultdict(list)
    c_sum = defaultdict(int, {colors[0]:1})
    for i in range(1, len(colors)):
        color = colors[i]
        dp[i] = dp[i-1]
        if color != colors[i-1]:
            dp[i] += c_sum[color]
            c_sum[color] = dp[i]
    print(dp[-1] % (10**9 + 7))

N = int(input())
colors = []
for _ in range(N):
    colors.append(int(input()))

search(colors)

Solution (Python):
N = int(input())
C = [int(input())]
cindex = {C[0]: 0}
mod = 7 + 10 ** 9
counter = 0
for _ in range(N-1):
    c = int(input())
    if c != C[-1]:
        C.append(c)
        counter += 1
        if c not in cindex:
            cindex[c] = counter

DP = [[0, 1] for i in range(len(C))]
for i in range(1, len(C)):
    if cindex[C[i]] == i:
        DP[i][1] = DP[i-1][1]
    else:
        DP[i][0] = DP[cindex[C[i]]][1] 
        DP[i][1] = DP[i][0] + DP[i-1][1]
        DP[i][1] %= mod
        cindex[C[i]] = i
print(DP[-1][1])

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

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

print(dp[N-1] % mod)

Solution (Python):
MOD = 10**9 + 7
N = int(input())
C = []
last_idx = [0 for i in range(200001)]
bef = [0 for i in range(N+1)]
for i in range(1,N+1):
	c = int(input())
	C.append(c)
	bef[i] = last_idx[c]
	last_idx[c] = i
dp = [0 for i in range(N+1)]
dp[1] = 1
if N == 1 or N == 2:
	print(1)
	exit()

for i in range(2, N+1):
	if bef[i] < i-1:
		dp[i] = (dp[i-1] + dp[bef[i]]) % MOD
	else:
		dp[i] = dp[i-1]
print(dp[N])

Solution (Python):
import sys
sy=sys.stdin.readline

n=int(sy())
if n==1:
    print(1)
    quit()
dp=[0]*(n+1)
lis=[0]*(2*10**5+1)
dp[0],dp[1],dp[2]=0,1,1
c1=int(sy())
c2=int(sy())
lis[c1]=1
lis[c2]=2
for i in range(3,n+1):
    c1=c2
    c2=int(sy())
    if c1==c2 or lis[c2]==0:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[lis[c2]]
    lis[c2]=i
    dp[i]%=1000000007
print(dp[n])

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

mod = 10 ** 9 + 7

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

M = len(D)

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

print(dp[-1] % mod)

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


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

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

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

dic = {}

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

print((ans+1)%mod)

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

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

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

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

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

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

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

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

print(dp[N-1])

Solution (Python):



MAX_C = 2 * 10 ** 5


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

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
c=[int(input()) for _ in range(n)]
x=[c[0]]
for i in range(1,n):
    if c[i]!=c[i-1]:
        x.append(c[i])


dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
res2=[0 for _ in range(max(x)+1)]
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])+res2[x[i]]
            
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
    res2[x[i]]+=dp[i-1]
    
print((dp[len(x)-1]+1)%(10**9+7))

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

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

sosu = 10 ** 9 + 7

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

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

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

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

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

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

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

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