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:
n = int(input())
c = [int(input()) for _i in range(n)]
c.append(-1)
dic = {}
dp = [0 for _i in range(n+1)]
dp[n] = 1
for i in range(n):
    if c[i-1] != c[i]:
        if c[i] in dic:
            dp[i] += dic[c[i]]
            dic[c[i]] += dp[i-1]
        else:
            dic[c[i]] = dp[i-1]
    dp[i] += dp[i-1]
print(dp[n-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [int(input()) for _i in range(n)]

dic = {}
dp = [0 for _i in range(n)]
dp[0] = 1
for i in range(1, n):
    if c[i-1] != c[i]:
        if c[i] in dic:
            dp[i] += dic[c[i]]
            dic[c[i]] += dp[i]
        else:
            dic[c[i]] = dp[i-1] + 1
    dp[i] += dp[i-1]
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [int(input()) for _i in range(n)]

dic = {}
dp = [0 for _i in range(n)]
dp[0] = 1
for i in range(1, n):
    if c[i-1] != c[i]:
        if c[i] in dic:
            dp[i] += dic[c[i]]
            dic[c[i]] += dp[i-1]
        else:
            dic[c[i]] = dp[i-1] + 1
    dp[i] += dp[i-1]
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect
n = int(input())
c = [int(input()) for i in range(n)]
a = []
s = set()
d = {}
for i,ci in enumerate(c):
  if ci in s:
    l = d[ci]
    a.append((l,i))
  else:
    s.add(ci)
  d[ci] = i
a.sort()
mod = 10**9+7
r = []
ans = 1
if a != []:
  for i,ai in enumerate(a):
    p,q = ai
    if q-p == 1:
      continue
    ans += 1
    if r != []:
      ans += bisect(r,p)
    r.append(q)
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect
n = int(input())
c = [int(input()) for i in range(n)]
a = []
s = set()
d = {}
for i,ci in enumerate(c):
  if ci in s:
    l = d[ci]
    if l+1 < i:
      a.append((l,i))
  else:
    s.add(ci)
  d[ci] = i
a.sort()
mod = 10**9+7
r = []
ans = 1
if a != []:
  for i,ai in enumerate(a):
    p,q = ai
    ans += 1
    if r != []:
      ans += bisect(r,p)%mod
    r.append(q)
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect
n = int(input())
c = [int(input()) for i in range(n)]
a = []
s = set()
d = {}
for i,ci in enumerate(c):
  if ci in s:
    l = d[ci]
    if l+1 < i:
      a.append((l,i))
  else:
    s.add(ci)
  d[ci] = i
a.sort()

r = []
ans = 1
if a != []:
  for i,ai in enumerate(a):
    p,q = ai
    ans += 1
    if r != []:
      ans += bisect(r,p)
    r.append(q)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect
n = int(input())
c = [int(input()) for i in range(n)]
a = []
s = set()
d = {}
for i,ci in enumerate(c):
  if ci in s:
    l = d[ci]
    a.append((l,i))
  else:
    s.add(ci)
  d[ci] = i
a.sort()

r = []
ans = 1
if a != []:
  for i,ai in enumerate(a):
    p,q = ai
    if q-p == 1:
      continue
    ans += 1
    if r != []:
      ans += bisect(r,p)
    r.append(q)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
    start_sort = [[-1,-1]]+sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(start_sort))
    for i in range(1,len(start_sort)):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,start_sort[i][0])
        j = e_ind[ends[ind-1]]
        dp[i] += dp[j]
        dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
            dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]-1])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_left(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
            dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    ends = [-1]
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
                ends.append(l[i+1])
    selist = [[-1,-1]]+sorted(selist,key=lambda x:x[1])
    # s_ind = {}
    # for i,(s,e) in enumerate(selist):
        # e_ind[e] = i
    # ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist))
    for i in range(1,len(selist)):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,selist[i][0])
        dp[i] += dp[ind-1]
    ans = dp[-1]+1
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
    start_sort = [[-1,-1]]+sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(start_sort))
    for i in range(1,len(start_sort)):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,start_sort[i][0])
        j = e_ind[ends[ind-1]]
        dp[i] += dp[j]
    ans = dp[-1]+1
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_right(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
    ans = dp[-1]+1
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]-1])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_left(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
    ans = dp[-1]+1
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def solve():
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]-1])
    selist.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        for j in range(i-1,0,-1):
            if selist[i-1][0]>selist[j-1][1]:
                dp[i] += dp[j]
                break
    ans = dp[-1]+1
    return ans
print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  if len(cdic[c])<10:
    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[mid]
        break
      elif cdic[c][mid]>=i:
        r=mid-1
      elif cdic[c][mid+1]<i:
        l=mid+1
      else:
        print("error")
    
#print(dp)
print(dp[-1]%MOD)

Submission status: Wrong Answer

Solution code:
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]]]
    t[c[i]] = i

print(dp[-1])

Submission status: Wrong Answer

Solution code:
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]]
    C[col].append(i)
print(dp[N-1])

Submission status: Wrong Answer

Solution code:
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]]
    C[col].append(i)
    print(dp)
print(dp[N-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
C = defaultdict(list)
dp = [0] * 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] += max(dp[C[col][-1]]*2, 1)
    C[col].append(i)
print(dp[N-1]+1)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def MOD_pow(a, n):
    res = 1
    while n > 0:
        if (n & 1):
            res = res * a % MOD
        a = a * a % MOD
        n = n // 2
    return res

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
    print(dp[len(d)-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
C = []
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.keys():
            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])

Submission status: Wrong Answer

Solution code:
n = int(input())
C = []
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:
            idx[C[i]] = i
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1]+dp[idx[C[i]]]
            idx[C[i]] = i
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

ans=0
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(l[:5],k[:5])
print(ans+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[int(input()) for i in range(N)]
C=[C[i] for i in range(N) if i ==0 or C[i-1]!=C[i]]

import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
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])

Submission status: Wrong Answer

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

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

ans=1
pre=-1
for _ in range(N):
    c=int(input())-1
    if pre==c:
        continue
    ans+=l[c]
    l[c]=ans
    pre=c

print(ans)

Submission status: Wrong Answer

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

ans=1
C=[]
num=[0]*2*10**5 #数を記録
temp=[0]*2*10**5 #足し算する数を残す

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

pre=-1
#上から決定していけばよい
for c in C:
    if pre==c:
        continue
    ans+=temp[c]
    temp[c]=ans
    #print(ans)
    #print(temp[:5])
    pre=c

print(ans)
    

#print(ans)

Submission status: Wrong Answer

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

ans=0
C=[]
num=[0]*2*10**5 #数を記録
temp=[0]*2*10**5 #足し算する数を残す

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

pre=-1
#上から決定していけばよい
for c in C:
    if pre==c:
        continue
    ans+=temp[c]
    temp[c]=(ans+1)
    #print(ans)
    #print(temp[:5])
    pre=c

print(ans+1)
    

#print(ans)

Submission status: Wrong Answer

Solution code:
#reversi
n=int(input())
lists=[]
for i in range(n):
    a=int(input())
    lists.append(a)
dp=[0 for i in range(n+1)]
dp[0]=1

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
    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]]
            before[a]=i+1
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=[0 for i in range(n)]
for i in range(n):
    a=int(input())
    lists[i]=a
dp=[0 for i in range(n+1)]
dp[1]=1

sum_dp=[0 for j  in range(n+1)]
sum_dp[1]=1

last_number={i:0 for i in range(2*10**5+1)}#最後に同じ三唱をした値を記録しておくための連想配列
last_number[lists[0]]=1

for i in range(1,n):
    k=lists[i]

    if k==lists[i-1]:
        dp[i+1]=dp[i]
        sum_dp[i+1]=sum_dp[i]
        last_number[k]=i+1
    else:
        if last_number[k]==0:
            dp[i+1]=dp[i]
            sum_dp[i+1]=dp[i+1]
            last_number[k]=i+1
        elif last_number[k]!=0:
            dp[i+1]=dp[i]+sum_dp[last_number[k]]
            sum_dp[i+1]=dp[i+1]
            last_number[k]=i+1
print(dp[n])

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

for i in range(N):
    if i == 0:
        dp[i] = 1
        last[C[i]] += dp[i]
        continue

    dp[i] = dp[i - 1] + last[C[i]]
    last[C[i]] += dp[i]
    dp[i] %= mod

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

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

last = defaultdict(lambda:-1)

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

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

print(dp[-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

N = int(input())

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

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

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

Submission status: Wrong Answer

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

INF = 10 ** 9

N = int(input())

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

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

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

Submission status: Wrong Answer

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

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

dp = [0]*N
dp[0] = 1
acc = [0]*(2*10**5+100)
acc[C[0]] = 1

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

print(dp[N-1])

Submission status: Wrong Answer

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

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

dp[0] = 1
prev_i[A[0]] = 0

for i in range(1, N):
  a = A[i]
  if prev_i[a] >= 0:
    if prev_i[a] == i - 1:
      dp[i] = dp[i - 1]
    else:
      dp[i] = dp[i - 1] + dp[prev_i[a]]
  else:
    dp[i] = dp[i - 1]
  prev_i[a] = i
  #print(i, dp, prev_i)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
 
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] != -1:
    if prev_i[a] != i - 1:
      dp[i] = dp[i - 1] + dp[prev_i[a]]
    else:
      dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1]
  prev_i[a] = i
  #print(i, dp, prev_i)

print(dp[-1])

Submission status: Wrong Answer

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

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

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


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

    return r[-1]


print(main())

Submission status: Wrong Answer

Solution code:
print("test")

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

M = max(C)
dp = [-1] * N # dp[i番目が変わらない累積]
c_to_i = [-1] * (M + 1)
MOD = 10**9+7

dp[0] = 1
c_to_i[C[0]] = 0

for i in range(1, N):
  c = C[i]
  prev_i = c_to_i[c]
  dp[i] = dp[i-1]
  c_to_i[c] = i
  
  if i > prev_i + 1 and prev_i != -1:
    dp[i] += dp[prev_i]
    dp[i] %= MOD
  print(dp)

Submission status: Wrong Answer

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

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