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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def dfs(stones, depth):
    if len(stones) <= 2:
        # print(" "*depth, stones, "leaf")
        return 1
    # print(" "*depth, stones)

    # ans1 はじめの石使わない
    # print(" "*depth, "ans1")
    ans1 = dfs(stones[1:], depth+1)

    # ans2 はじめの石を使う
    c = stones[2:].count(stones[0])
    if c == 0:
        ans2 = 0
    else:
        ind = stones[2:].index(stones[0])
        # print(" "*depth, "ans2", c)
        # print(" "*depth, ind, stones, stones[ind:])
        ans2 = dfs(stones[2+ind:], depth+1)

    return (ans1 + ans2) % MOD


def solve(N: int, C: "List[int]"):
    print(dfs(C, 0) % MOD)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, C)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = []
di = {}

def per_count(x):
    if x>1:
        return int((x*(x-1))/2)
    else:
        return 0

for i in range(n):
    a = int(input())
    ls.append(a)
    if a in di:
        if a != ls[i-1]:
            di[a] = di.get(a) + 1
    else:
        di[a] =1
ans = 0
temp=[]
for p in di:
    ans += per_count(di.get(p))
    temp.append([i for i,x in  enumerate(ls) if x == p])

for q in range(1,len(temp)):
    for j in range(1,len(temp)):
        if max(temp[q-1]) < min(temp[j]):
            ans+=1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [0]
c = [int(input()) for i in range(N)]
C = C+c
ans = 1
dp = [0] * (N + 100)
color = [[]for i in range((2*(10**5)+100))]
dp[0] = 1

dp[1] = 1
color[C[1]].append(1)
for i in range(2, N+1):
    dp[i] = dp[i - 1]

    # dp[i]+=~~
    for col in reversed(color[C[i]]):
        #print(i, col-1)
        if i - col == 1:
            break
        else:
            dp[i] += dp[col-1]
    # forの最後でいい
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)
# print(dp)
print(dp[N])


# pypyで

Submission status: Wrong Answer

Solution code:
n = int(input())

mod = 10**9 + 7

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

print(res % mod)

Submission status: Wrong Answer

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

from collections import Counter, defaultdict

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

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

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

colors = removeonly1(compress(c))


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

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

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

Submission status: Wrong Answer

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

d = defaultdict(lambda:[])
for i in range(len(S)):
    d[S[i]].append(i)

val = [0]*(len(S)+1)
val[-1]=1
def rec(n):
    if val[n] != 0:
        return val[n]
    s = S[n]
    res = rec(n+1)
    l = d[s]
    i = bisect.bisect(l,n)
    for j in range(i,len(l)):
        res += rec(l[j]+1)
        res %= mod
    val[n]=res
    return res
print(rec(0))

Submission status: Wrong Answer

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

from collections import Counter, defaultdict

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

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

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

colors = removeonly1(compress(c))


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

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

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

Submission status: Wrong Answer

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

ans = 1

D = {}
for i in range(N) :
    if str(L[i]) not in D :
        D[str(L[i])] = 1
    else :
        if L[i-1] == L[i] :
            ans += (D[str(L[i])]-1)
            D[str(L[i])] += 1
        else :
            ans += D[str(L[i])]
            D[str(L[i])] += 1
ans %= (10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[[]for i in range(2*10**5+1)]
d=[1]
s[int(input())].append(0)
for i in range(1,n):
    j=int(input())
    t=0
    s[j].append(i)
    if len(s[j])>1:
        if s[j][-2]!=s[j][-1]-1:
            t+=d[i-1]+d[s[j][-2]]
        else:
            t+=d[i-1]
    else: 
        t+=d[i-1]
    d.append(t)
print(d[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import itertools
from functools import reduce


def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  counts = tuple(s_count.values())
  return counts

N = int(input())
string = input()

def search(N, string):
    memo = {}
    def count(counts, num_set):
        if (counts, num_set) in memo:
            return memo[(counts, num_set)]

        if num_set == 1:
            ans = sum(counts)
        elif num_set == 2:
            num_sum = sum(counts)
            ans = 0
            for i in range(len(counts)):
                num_sum -= counts[i]
                ans += counts[i] * num_sum
        else:
            ans = 0
            for i in range(len(counts) - 1):
                ans += counts[i] * count(counts[i + 1:], num_set - 1)

        memo[(counts, num_set)] = ans
        return ans

    counts = analyze(string)
    ans = 0
    for i in range(1, len(counts) + 1):
        ans += count(counts, i)
    print(ans % (10**9 + 7))

search(N, string)

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
last = -1
for i in range(n):
    C = int(input())
    if C != last:
        c.append(C)
        last = C
m = len(c)
index = [[] for i in range(max(c))]
for i in range(m):
    index[c[i] - 1].append(i)
kokomade = [0] * m
kokokara = [0] * m

for i in index:
    if len(i) >= 2:
        for j in i[1:]:
            kokomade[j] += 1
kokomade_t = [0]
for i in range(m):
    kokomade_t.append(kokomade[i] + kokomade_t[i])
kokomade = kokomade_t[1:]

for i in index:
    if len(i) >= 2:
        for j in i[:-1]:
            kokokara[j] += 1
kokokara.reverse()
kokokara_t = [0]
for i in range(m):
    kokokara_t.append(kokokara[i] + kokokara_t[i])
kokokara = kokokara_t[1:]
kokokara.reverse()

ans = 1
count = 0
for i in index:
    if len(i) >= 2:
        ans += len(i) - 1
        for j in i[:-1]:
            count += kokomade[j]
        for j in i[1:]:
            count += kokokara[j]
ans += count // 2
print(ans % (10 ** 9 + 7))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

d = defaultdict(lambda:deque([]))
for i in range(len(S)):
    d[S[i]].append(i)

val = [0]*(len(S)+1)
val[-1]=1
def rec(n):
    if val[n] != 0:
        return val[n]
    s = S[n]
    res = rec(n+1)
    que = d[s]
    for m in que:
        if n<m:
            res += rec(m+1)
            res %= mod
    val[n]=res
    return res
print(rec(0))

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
last = -1
for i in range(n):
    C = int(input())
    if C != last:
        c.append(C)
        last = C
m = len(c)
index = [[] for i in range(max(c))]
for i in range(m):
    index[c[i] - 1].append(i)
kokomade = [0] * m
kokokara = [0] * m

for i in index:
    if len(i) >= 2:
        for j in i[1:]:
            kokomade[j] += 1
kokomade_t = [0]
for i in range(m):
    kokomade_t.append(kokomade[i] + kokomade_t[i])
kokomade = kokomade_t[1:]

for i in index:
    if len(i) >= 2:
        for j in i[:-1]:
            kokokara[j] += 1
kokokara.reverse()
kokokara_t = [0]
for i in range(m):
    kokokara_t.append(kokokara[i] + kokokara_t[i])
kokokara = kokokara_t[1:]
kokokara.reverse()

ans = 1
count = 0
for i in index:
    if len(i) >= 2:
        ans += len(i) - 1
        for j in i[:-1]:
            count += kokomade[j]
        for j in i[1:]:
            count += kokokara[j]
ans += count // 2
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

MOD = int(1e9) + 7


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

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

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

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

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

for i in range(Nc):
    clists[i].sort()

P = [0]*N
Q = [0]*N
Q[0] = 1
for i in range(1,N):
    if C[i] == C[i-1]:
        Q[i] = 0
    else:
        Q[i] = P[i-1] + Q[i-1]
    
    m = bisect.bisect_left(clists[ui[C[i]]],i)
    P[i] = sum([Q[k] for k in clists[ui[C[i]]][:m]])

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

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
subC = [-2] * (2 * 10 ** 5 + 10)
cntC = [-1]*N
for num, i in enumerate(C):
    cntC[num] = subC[i]+1
    subC[i] = num

# print(cntC)

dp = [0] * (N + 10)
dp[0] = 1
for i in range(N):
    if cntC[i] < 0 or cntC[i] == i:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[cntC[i]]


print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
subC = [-2] * (2 * 10 ** 5 + 10)
cntC = [-1]*N
for num, i in enumerate(C):
    cntC[num] = subC[i]+1
    subC[i] = num

print(cntC)

dp = [0] * (N + 10)
dp[0] = 1
for i in range(N):
    if cntC[i] < 0 or cntC[i] == i:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[cntC[i]]


print(dp[N])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools
N=int(input())
C=[]
C.append(int(input()))
for i in range(N-1):
    c=int(input())
    if C[-1]!=c:
        C.append(c)



def returnAllIndex(C):
    retval={}
    for i,c in enumerate(C):
        tmp=retval.get(c,[])
        tmp.append(i)
        retval[c]=tmp
    return retval

retval=[]

def solve(C):
    retval.append(C)
    if len(C)==len(set(C)):
        return

    allIndex=returnAllIndex(C)

    for color in allIndex:
        count=len(allIndex[color])
        if count>1:
            for i in itertools.combinations([j for j in range(count)],2):
                p,q=i
                solve(C[:allIndex[color][p]:]+C[allIndex[color][q]::])
    return

solve(C)
print(len(set(list(map(tuple,retval)))))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
C = [0] * N
cindex = dict()
mod = 7 + 10 ** 9
for i in range(N):
    C[i] = int(input())
    if C[i] in cindex:
        cindex[C[i]].append(i)
    else:
        cindex[C[i]] = [i]

def variation(i, memo = {}):
    if i == N: return 1
    try:
        return memo[i]
    except KeyError:
        total = 0
        L = cindex[C[i]]
        flag = i
        for l in L:
            if l > flag + 1:
                total += variation(l + 1, memo) #lまで塗る
                total %= mod
                flag = l
        total += variation(i + 1, memo)
        total %= mod
        memo[i] = total
        return total

memo = {}
print(variation(0, memo))

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
C = []

for i in range(N):
    C.append(int(raw_input()))

S = 0
i = 0
while i < N:
    j = i+1
    flag = -1
    while j < N:
        if C[i] == C[j] and C[i]!=flag:
            S += 1
            flag = C[i]
        else:
            flag = -1
        j += 1
    i += 1

print (S+1)%(10**9+7)

Submission status: Wrong Answer

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

def inpl(): return list(map(int, input().split()))
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]
    else:
        DP[i] = DP[i-1]
    ixs[c].append(i)
print(DP[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict


def main():
    # n,m = [int(z) for z in input().split()]
    # table =[
    #     [int(z) for z in input().split()]
    #     for _ in range(n)
    # ]
    n = int(input())
    c = [int(input()) for _ in range(n)]

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

    D = defaultdict(lambda: [])

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

        pre = D[ci]
        res = table[i]
        for p_index in pre:
            res += table[p_index]
        table[i + 1] = res

        D[ci].append(i)

    print(table[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
# B
N = int(input())
C_list = [0]*N
for i in range(N):
    C_list[i] = int(input()) - 1
    
T = 1
DP = [0]*(max(C_list) + 1)

for i in range(N):
    c = C_list[i]
    if i > 0:
        if C_list[i] == C_list[i-1]:
            pass
        else:
            T, DP[c] = T + DP[c], DP[c] + T
    else:
        T, DP[c] = T + DP[c], DP[c] + T
print(T)

Submission status: Wrong Answer

Solution code:
import math

n=int(input())
l=[]
for i in range(n):
	l.append(int(input()))

col=[]
prev=-1
for i in range(200000):
	col.append(0)
for i in range(n):
	if l[i]!=prev:
		col[l[i]-1]+=1
	prev=l[i]

ans=0
p=1000000007
for i in range(200000):
	if col[i]>1:
		ans+=(col[i]*(col[i]-1)//2)%p
	ans=ans%p

ans+=1
ans=ans%p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0] * (N + 1)
dp[0] = 1

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

print(dp[N - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0] * (N + 1)
dp[0] = 1

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

print(dp[N - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import defaultdict
from bisect import bisect_right
last = -1
dic = defaultdict(list)
idx = 0
lis = []
for i in range(N):
    c = int(input())
    if c==last:
        continue
    last = c
    dic[c].append(idx)
    lis.append(c)
    idx += 1
memo = {}
memo_s = set()
def dfs(i):
    if i==idx:
        return 1
    if i in memo_s:
        return memo[i]
    v = lis[i]
    ret = 0
    n_idx = bisect_right(dic[v], i)
    if n_idx<len(dic[v]):
        for nx in dic[v][n_idx:]:
            ret += dfs(nx+1)
            ret %= mod
    ret += dfs(i+1)
    ret %= mod
    memo[i] = ret
    memo_s.add(i)
    return ret
print(dfs(0))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import defaultdict
from bisect import bisect_right
last = -1
dic = defaultdict(list)
idx = 0
lis = []
for i in range(N):
    c = int(input())
    if c==last:
        continue
    last = c
    dic[c].append(idx)
    lis.append(c)
    idx += 1
memo = {}
def dfs(i):
    if i==idx:
        return 1
    if i in memo.keys():
        return memo[i]
    v = lis[i]
    ret = 0
    n_idx = bisect_right(dic[v], i)
    if n_idx<len(dic[v]):
        for nx in dic[v][n_idx:]:
            ret += dfs(nx+1)
            ret %= mod
    ret += dfs(i+1)
    ret %= mod
    memo[i] = ret
    return ret
print(dfs(0))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import defaultdict
last = -1
dic = defaultdict(list)
idx = 0
lis = []
for i in range(N):
    c = int(input())
    if c==last:
        continue
    last = c
    dic[c].append(idx)
    lis.append(c)
    idx += 1
memo = {}
def dfs(i):
    if i==idx:
        return 1
    if i in memo.keys():
        return memo[i]
    v = lis[i]
    ret = 0
    for nx in dic[v]:
        if nx<=i: continue
        ret += dfs(nx+1)
        ret %= mod
    ret += dfs(i+1)
    ret %= mod
    memo[i] = ret
    return ret
print(dfs(0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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)] + [None]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    colors = defaultdict(list)
    for i, c in enumerate(C):
        colors[c].append(i)

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        # i個目を塗らない
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        for j in colors[C[i]]:
            if j <= i:
                continue

            # ぬる
            dp[j + 1] += dp[i]
            dp[j + 1] %= MOD

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    C=[int(input())for _ in range(n)]
    places=[[] for _ in range(2*10**5+1)]
    for i in range(n):
        places[C[i]].append(i)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=(dp[i]+dp[i-1])%mod
        color=C[i-1]
        it=places[color].index(i-1)
        if it>0:
            j=places[color][it-1]
            if i-1-j>1:
                dp[i]=(dp[i]+dp[j+1])%mod
    print(dp[-1])


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline

MOD = 10 ** 9 + 7


BIT_len = 2 ** 18 # = 262144 > 200000
BIT_MOD = np.zeros(BIT_len+1, np.int64)

def BIT_add(index, elem):
    global BIT_len, BIT_MOD
    index += 1
    while index <= BIT_len:
        BIT_MOD[index] += elem
        BIT_MOD[index] %= MOD
        index += index & -index

def BIT_sum(index):
    global BIT_len, BIT_MOD
    index += 1
    s = 0
    while index != 0:
        s += BIT_MOD[index]
        s %= MOD
        index -= index & -index
    return s


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


BIT_add(0, 1)
for start, end in pairs:
    BIT_add(end, BIT_sum(start))

print(BIT_sum(N))

Submission status: Time Limit Exceeded

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

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

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

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

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  for j in reversed(cdic[c]):
    if j<i:
      dp[i]+=dp[j]
      break
    
#print(dp)
print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(list)
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]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]

  table[x].append(N-1-i)

print(dp[0]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(list)
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]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
    dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(list)
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]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
  dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])