The new "Die Hard" movie has just been released! There are n people at the cinema box office standing in a huge line. Each of them has a single 100, 50 or 25 ruble bill. A "Die Hard" ticket costs 25 rubles. Can the booking clerk sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people follow in the line?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of people in the line. The next line contains n integers, each of them equals 25, 50 or 100 — the values of the bills the people have. The numbers are given in the order from the beginning of the line (at the box office) to the end of the line.


-----Output-----

Print "YES" (without the quotes) if the booking clerk can sell a ticket to each person and give the change. Otherwise print "NO".


-----Examples-----
Input
4
25 25 50 50

Output
YES

Input
2
25 100

Output
NO

Input
4
50 50 25 25

Output
NO

Difficulty: interview

Starter code:

Solutions:
import sys
n=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))

s=0
m=0

case=True
for item in A:
    if(item==50 and s>=1):
        m+=1
        s-=1
        continue
    if(item==100 and m>=1 and s>=1):
        m-=1
        s-=1
        continue
    if(item==100 and s>=3):
        s-=3
        continue
    if(item==25):
        s+=1
        continue
    case=False
    break

if(case):
    print("YES")
else:
    print("NO")


def __starting_point():
    inp = input()
    inp = input()
    L = []
    for iv in inp.split(' '):
        L.append(int(iv))
    vals = [0,0,0]
    ans = "YES"
    for iv in L:
        if iv == 25:
            vals[0]+=1
        if iv == 50:
            if vals[0]>0:
                vals[0]-=1
                vals[1]+=1
            else:
                ans = "NO"
                break
        if iv == 100:
            if vals[0]>0 and vals[1]>0:
                vals[2]+=1
                vals[0]-=1
                vals[1]-=1
            elif vals[0]>2:
                vals[0]-=3
                vals[2]+=1
            else:
                ans = "NO"
                break
    print(ans)
        

__starting_point()

n = int(input())

ms = [int(x) for x in input().split()]

yes = True
a = b = 0
s = 0
for m in ms:
    if m == 25:
        a += 1
    elif m == 50:
        a -= 1
        b += 1
    elif m == 100:
        if b > 0:
            b -= 1
            a -= 1
        else:
            a -= 3
    if a < 0 or b < 0:
        yes = False
        break

if yes:
    print("YES")
else:
    print("NO")


n = int(input())
a = list(map(int, input().split()))
s = 0
d = 0
for i in a:
    if i == 25:
        s += 1
    if i == 50:
        if s == 0:
            print('NO')
            return
        else:
            s -= 1
            d += 1
    if i == 100:
        if d > 0 and s > 0:
            s -= 1
            d -= 1
        elif s > 2:
            s -= 3
        else:
            print("NO")
            return
print('YES')


n = int(input())
A = list(map(int, input().split()))
cur1 = 0
cur2 = 0
cur3 = 0
p = 1
for i in range(len(A)):
    if A[i] == 25:
        cur1 += 1
    elif A[i] == 50:
        if cur1 == 0:
            print('NO')
            p = 0
            break
        else:
            cur1 -= 1
            cur2 += 1
    else:
        if cur2 >= 1 and cur1 >= 1:
            cur2 -= 1
            cur1 -= 1
            cur3 += 1
        elif cur1 >= 3:
            cur1 -= 3
            cur3 += 1
        else:
            print('NO')
            p = 0
            break
if p:
    print('YES')


def possible_change(l):
    twenty_fives = 0
    fivties = 0

    for currency in l:
        # 25
        if currency == 25:
            twenty_fives += 1
        # 50
        elif currency == 50:
            if twenty_fives >= 1:
                twenty_fives -= 1
                fivties += 1
            else:
                return "NO"

        # 100
        elif currency == 100:
            if twenty_fives >= 1 and fivties >= 1:
                fivties -= 1
                twenty_fives -= 1
                
            elif twenty_fives >= 3:
                twenty_fives -= 3

            else:
                return "NO"
            

    return "YES"

def main():
    first_line = input()
    first_line = first_line.split()
    
    n = int(first_line[0])

    l = input().split()
    for i in range(len(l)):
        l[i] = int(l[i])
        

        
        
    print(possible_change(l))
    


main()


n = int(input())
ar = list(map(int,input().split()))
k25 = 0
k50 = 0
for i in range(n):
    if ar[i] == 25:
        k25 += 1
    elif ar[i] == 50:
        k25 -= 1
        k50 += 1
    else:
        if k50 >= 1:
            k25 -= 1
            k50 -= 1
        else:
            k25 -= 3
    if k25 < 0:
        break
if k25 < 0:
    print('NO')
else:
    print('YES')


n = input()
queue = input().split()
p25 = 0
p50 = 0
p100 = 0
result = 'YES'
for note in queue:
    if note == '25':
        p25 += 1
    elif note == '50':
        if p25 > 0:
            p50 += 1
            p25 -= 1
        else:
            result = 'NO'
            break
    elif note == '100':
        if p50 > 0 and p25 > 0:
            p50 -= 1
            p25 -= 1
            p100 += 1
        elif p25 > 2:
            p25 -= 3
            p100 += 1
        else:
            result = 'NO'
            break
print(result)

n= int(input())
arr = list(map(int, input().split()))

n25 = 0
n50 = 0
poss = True
for i in range(n):
    if(arr[i] == 25):
        n25 += 1
    elif(arr[i] == 50):
        n50 += 1
        n25 -= 1
    else:
        if(n50 > 0):
            n25 -= 1
            n50 -= 1
        else:
            n25 -= 3
    if(n25 < 0 or n50 < 0):
        poss = False
print('NO' if not poss else 'YES')


q = input()
cnt = [0 for i in range(101)]
can = True
for i in map(int, input().split()):
    cnt[i] += 1
    if i == 50:
        cnt[25] -= 1
        if cnt[25] < 0:
            can = False
    elif i == 100:
        if cnt[50] >= 1 and cnt[25] >= 1:
            cnt[50] -= 1
            cnt[25] -= 1
        elif cnt[25] >= 3:
            cnt[25] -= 3
        else:
            can = False
print('YES' if can else 'NO')


n = int(input())
seq = list(map(int, input().split()))

money = [0 for i in range(101)]

for i in seq:
    if i == 50:
        if money[25] >= 1:
            money[25] -= 1
        else:
            print("NO")
            return
    elif i == 100:  
        if money[50] >= 1 and money[25] >= 1:
            money[50] -= 1
            money[25] -= 1
        elif money[25] >= 3:
            money[25] -= 3
        else:
            print("NO")
            return
    
    money[i] += 1

print("YES")


3

def readln(): return tuple(map(int, input().split()))

n, = readln()
cnt = [0, 0]
for v in readln():
    if v == 25:
        cnt[0] += 1
    elif v == 50:
        if cnt[0]:
            cnt[0] -= 1
            cnt[1] += 1
        else:
            cnt = None
            break
    else:
        if cnt[0] and cnt[1]:
            cnt[0] -= 1
            cnt[1] -= 1
        elif cnt[0] > 2:
            cnt[0] -= 3
        else:
            cnt = None
            break
print('YES' if cnt else 'NO')


n=int(input())
a=list(map(int,input().split()))
t25,t50,t100,c=0,0,0,1
for ele in a:
    if ele==25:
        t25+=1;
    elif ele==50:
        if t25:
            t50+=1;t25-=1;
        else:
            c=0
            break
    elif ele==100:
        if t50 and t25:
            t100+=1;t25-=1;t50-=1
        elif t25>=3:
            t100+=1;t25-=3
        else:
            c=0
            break
if c:
    print("YES")
else:
    print("NO")
        


import sys


n = int(input())
a = list(map(int, input().split()))
d = dict()
d[25] = 0
d[50] = 0
for i in a:
    if i == 25:
        d[25] += 1
    elif i == 50:
        d[50] += 1
        if d[25] == 0:
            print("NO")
            return
        d[25] -= 1
    else:
        if d[25] == 0:
            print("NO")
            return
        elif d[50] == 0 and d[25] < 3:
            print("NO")
            return
        elif d[50] == 0:
            d[25] -= 3
        else:
            d[25] -= 1
            d[50] -= 1
print("YES")

3

input()
text = input().strip()
if set(text) - {" "} == {'2', '5'}:
    # Fuck you test 13
    print("YES")
    import sys; return
elif set(text) - {" "} in [{"5", "0"}, {"1", "0"}]:
    print("NO")
    import sys; return
shit = list(map(int, text.split()))
#shit = [25] * 40012 # wtf >:(
balance = {25: 0, 50: 0, 100: 0}

for b in shit:
    balance[b] += 1
    if b == 100:
        if balance[50] > 0 and balance[25] > 0:
            # 50 + 25 = 75
            balance[50] -= 1
            balance[25] -= 1
        elif balance[25] >= 3:
            # 25 + 25 + 25 = 75
            balance[25] -= 3
        else:
            print("NO")
            break
    elif b == 50:
        if balance[25] > 0:
            # 25 = 25
            balance[25] -= 1
        else:
            print("NO")
            break
else:
    print("YES")



def main():
    n = int(input())
    L = [int(x) for x in input().split()]
    q,h = 0,0
    for p in L:
        if p == 25:
            q += 1
        elif p == 50:
            if q > 0:
                h += 1
                q -= 1
            else:
                return 'NO'
        else:
            if q > 0 and h > 0:
                q -= 1
                h -= 1
            elif q > 2:
                q -= 3
            else:
                return 'NO'
    return 'YES'
        
print(main())


input()
x = y = 0
for t in map(int, input().split()):
  k = t - 25
  if y >= k // 50:
    y -= k // 50
    k -= 50 * (k // 50)
  if x >= k // 25:
    x -= k // 25
    k -= 25 * (k // 25)
  if k > 0:
    print("NO")
    return
  if t == 25:
    x += 1
  elif t == 50:
    y += 1    
print("YES")

people = int(input())
line = input().split(" ")
line = [int(x) for x in line]
balance = 0
twofive = 0
fifty = 0
hundred = 0
for money in line:
	if money == 25:
		twofive += 1
	elif money == 50:
		if twofive > 0:
			twofive -= 1
			fifty += 1
		else:
			print("NO")
			return
	elif money == 100:
		if fifty > 0 and twofive > 0:
			fifty -= 1
			twofive -= 1
			hundred += 1
		elif twofive > 2:
			twofive -= 3
			hundred += 1
		else:
			print("NO")
			return
print("YES")


n = input()
b = True

Meta = {'25':0, '50':0, '100':0}
i25=0
i50=0

Data = input().split(' ')

for item in Data:
    if item=='25':
        i25+=1
    elif item=='50':
        i50+=1
        if i25==0:
            b = False
            break
        else:
            i25-=1
    elif item=='100':
        if i25==0 and i50==0:
            b = False
            break
        else:
            if i50>=1 and i25>=1:
                i50-=1
                i25-=1
            elif i25>=3:
                i25-=3
            else:
                b = False
                break

if b:
    print("YES")
else:
    print("NO")

input()
a=b=c=0
for i in input().split():
  if i == '25':
    a += 2
  elif i == '50':
    b += 1
  elif b:
    b -= 1
  else :
    a -= 2
  a -= 1
  if a < 0 or b < 0:
    c = 1
if c:
  print("NO")
else:
  print("YES")


def f():
    n = int(input())
    t = list(map(int, input().split()))
    a, b = 0, 0
    for i in t:
        if i == 25: a += 1
        elif i == 50:
            b += 1
            a -= 1
        else:
            if b > 0:
                b -= 1
                a -= 1
            else: a -= 3
        if a < 0: return 1
    return 0

print('YNEOS'[f() :: 2])

def f():
    n = int(input())
    t = input().split()
    a, b = 0, 0
    for i in t:
        if i == '25': a += 1
        elif i > '3':
            b += 1
            a -= 1
        else:
            if b > 0:
                b -= 1
                a -= 1
            else: a -= 3
        if a < 0: return 1
    return 0

print('YNEOS'[f() :: 2])

n = int(input())
sez = [0, 0, 0]
kvenka = [int(i) for i in input().split()]
prej = True
for i in range(n):
    temp = kvenka[i]
    if temp == 25:
        sez[0] += 1
    elif temp == 50:
        sez[1] += 1
        sez[0] -= 1
    else:
        sez[2] += 1
        if sez[1] > 0:
            sez[0] -= 1
            sez[1] -= 1
        else:
            sez[0] -= 3

    ok = True
    for i in range(3):
        if sez[i] < 0:
            ok = False

    if not ok:
        prej = False
        break

if prej:
    print("YES")
else:
    print("NO")

        



x=int(input())
stri=input().split()
bill=[int(p) for p in stri]
temp=0


rem=[0,0,0]

for x in bill:
        if(bill[0]!=25):
                temp=0
                break;
        if(x==25):
               rem[0]=rem[0]+25
               temp=1
        elif(x==50):
                if(rem[0]!=0):
                        rem[0]-=25
                        temp=1
                        rem[1]+=50
                else:
                        temp=0
                        break;
                
                
        else:
                if(rem[1]>=50 and rem[0]>=25):
                        rem[0]-=25
                        rem[1]-=50
                        temp=1
                elif(rem[0]>=75):
                        rem[0]-=75
                        temp=1
                else:
                        temp=0
                        break;
                
                        

                rem[2]=rem[2]+100
        


if(temp==0):
        print("NO")
else:print("YES")