Problem:
 Score : 1200 points    Problem Statement There are N arrays.
The length of each array is M and initially each array contains integers (1，2，...，M) in this order.  Mr. Takahashi has decided to perform Q operations on those N arrays.
For the i -th ( 1≤i≤Q ) time, he performs the following operation.   Choose an arbitrary array from the N arrays and move the integer a_i ( 1≤a_i≤M ) to the front of that array. For example, after performing the operation on a_i=2 and the array (5，4，3，2，1) , this array becomes (2，5，4，3，1) .   Mr. Takahashi wants to make N arrays exactly the same after performing the Q operations.
Determine if it is possible or not.      Constraints  2≤N≤10^5  2≤M≤10^5  1≤Q≤10^5  1≤a_i≤M         Input The input is given from Standard Input in the following format:  N  M  Q  a_1  a_2  ...  a_Q       Output Print Yes if it is possible to make N arrays exactly the same after performing the Q operations.
Otherwise, print No .        Sample Input 1 2 2
3
2 1 2      Sample Output 1 Yes  You can perform the operations as follows.        Sample Input 2 3 2
3
2 1 2      Sample Output 2 No       Sample Input 3 2 3
3
3 2 1      Sample Output 3 Yes  You can perform the operations as follows.        Sample Input 4 3 3
6
1 2 2 3 3 3      Sample Output 4 No

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

import sys
from itertools import product
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*M + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    used = set()
    ch = []
    for i in range(M):
        if table[i] < N:
            break
        ch.append(stack[i])
        used.add(stack[i])
    for i in range(M):
        if i not in used:
            used.add(i)
            ch.append(i)
    
    return stack == ch

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    if not check2(A):
        ans = 'No'
print(ans)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_e

最後の配列の状態は何で決定されるか。
同じaが同じ配列に複数回採用されたとき、効果があるのは最後に
採用したaのみ。(それ以前は合っても無くても同じになる)

最初、1が採用状態になっていると考えてよい。
→おそらく気にすべきは配列aのみ(Nこの配列は考慮しなくてよい)

1以外は、出現するなら少なくともN個出現しなければ不可能
2,3だけで考えてみよう

N==3のとき

322233 →不可能(2が先頭が1つ生まれてしまう)
232233 →可能

→終了後の配列の数字は、最後に出現した順に前から並ぶ
→よってaを見れば構成後の数列は分かる

→後ろからaを見ていって、先に登場したやつより後に登場したほうが数が越えたらダメ
→ただし、N個目以降は完全無視する
→終了時に数がNに達していないのがあったらダメ(1を除く？)

いや例3…
→初期状態、の扱い方を考え直さなきゃな…

aの前に M…M(N個),M-1…M-1,…,1…1 があると考える
すると、aを後ろから見ていった時に先に登場したやつより後に登場したほうが数が越えてはいけない、
だけの条件になる！！

あ、2233223 は…？
最後の2つの2を1箇所に適応すれば可能じゃん！
lis[a[i][0]]ってなんだ…？
→それ以降に先頭をa[i][0]に更新できる最大数
→よって、indに対して単調減少になっていなければいけない

うん？前を超えないようにして、最終的にすべてN以上になればおｋ？
"""
import sys
N,M = map(int,input().split())

Q = int(input())

A = list(map(int,input().split()))

dic = {}
lis = []
flag = True

a = [[M-i,N] for i in range(M)]
for i in range(Q):
    a.append([A[i],1])
a.reverse()


for i in range(len(a)):

    if a[i][0] not in dic:
        ind = len(dic)
        dic[a[i][0]] = ind
        if ind != 0:
            lis.append(min(lis[ind-1] , a[i][1]))
        else:
            lis.append(a[i][1])
    else:
        ind = dic[a[i][0]]
        if ind != 0:
            lis[ind] = min(N, lis[ind] + a[i][1] , lis[ind-1])
        else:
            lis[ind] = min(N, lis[ind] + a[i][1])

if lis[-1] == N:
    print ("Yes")
else:
    print ("No")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
Q = int(input())
A = [int(x) for x in input().split()]

used = [False] * (M+1)
arr = []
for x in A[::-1]:
    if used[x]:
        continue
    used[x] = True
    arr.append(x)
for x in range(1,M+1):
    if used[x]:
        continue
    arr.append(x)

x_to_i = {x:i for i,x in enumerate(arr,1)}

made = [N] + [0] * M

for x in A[::-1]:
    i = x_to_i[x]
    if made[i-1] > 0:
        made[i-1] -= 1
        made[i] += 1

L = 0
prev = M+100
for x in arr[::-1]:
    if x >= prev:
        break
    prev = x
    L += 1

x = sum(made[::-1][:L+1])
answer = 'Yes' if x == N else 'No'
print(answer)

Solution (Python):
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
	elif (freq[pos[i]] > 0):
		freq[pos[i]] -= 1
		freq[pos[i]+1] += 1
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Solution (Python):
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Solution (Python):
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
start = M
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Solution (Python):

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	sa = set(a)
	seen = set()
	r = []
	for n in a[::-1]:
		if n not in seen:
			r.append(n)
			seen.add(n)
	for i in range(m):
		if (i+1) not in sa:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = m
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    q = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, q))
    a = [x - 1 for x in a]
    l = [[] for i in xrange(m)]
    la = []
    for i in xrange(q - 1, -1, -1):
        x = a[i]
        if not l[x]:
            la.append(x)
        l[x].append(i)
    ok = 1
    b = [q] * n
    f = [0] * m
    xt = 0
    for i, x in enumerate(la):
        j = 0
        for y in l[x]:
            if j < n and y < b[j]:
                b[j] = y
                j += 1
        if j < n:
            ok = 0
            b[j] = -1
        if not ok:
            while f[xt]:
                  xt += 1
            if x != xt:
                print "No"
                return
            f[xt] = 1
        else:
            f[x] = 1
    print "Yes"
main()