Problem:


Score : 300 points

Problem Statement

You are given an array A of length N.
Your task is to divide it into several contiguous subarrays.
Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order.
At least how many subarrays do you need to divide A into?

Constraints

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Each A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible number of subarrays after division of A.

Sample Input 1

6
1 2 3 2 2 1

Sample Output 1

2

One optimal solution is to divide the array into [1,2,3] and [2,2,1].

Sample Input 2

9
1 2 1 2 1 2 1 2 1

Sample Output 2

5

Sample Input 3

7
1 2 3 2 1 999999999 1000000000

Sample Output 3

3



Sample input:
6
1 2 3 2 2 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

count=1

j=0
for i in range(N+1):
  k=i
  if (A[j:k]==sorted(A[j:k]) or A[j:k]==sorted(A[j:k],reverse=True)):
    continue
  else:
    count+=1
    j=i-1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = 0
ans = 1

for i in range(n):
    if a[x:i+1] != sorted(a[x:i+1]) and a[x:i+1] != sorted(a[x:i+1], reverse = True):
        x = i
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    i = 1

    while i < len(A) - 1:
        if (A[i - 1] < A[i] and A[i] > A[i + 1]) or (A[i - 1] > A[i] and A[i] < A[i + 1]):
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    i = 1

    while i < len(A) - 1:
        if A[i - 1] < A[i] and A[i] > A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        elif A[i - 1] > A[i] and A[i] < A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
K=0
R=list()
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  R.append(L[i])
  A=sorted(R)
  M=sorted(R, reverse=True)
  if A!=R and M!=R:
    K=K+1
    R=list()
    R.append(L[i])
K=K+1
print(K)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 1
i = -1
flg = True
while True:
  i += 1
  if i >= n-1:
    break
  if a[i] < a[i+1]:
    flg = True
  elif a[i] > a[i+1]:
    flg = False
  else:
    continue
  for k in range(i, n-1):
    if (flg and a[k] > a[k+1]) or ((not flg) and a[k] < a[k+1]):
      cnt += 1
      i = k
      break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))+[0]
a=[a[i] for i in range(n) if a[i]!=a[i+1]]
s=0
while a:
  n=len(a)
  if n==1:
    a=[]
  else:
    d=a[0]-a[1]>0
    for i in range(n-1):
      if d==(a[i]-a[i+1]<0):
        a=a[i+1:]
        break
    else:
      a=[]
  s+=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
line = [int(x) for x in input().split(' ')]
count = 1
prev = line[0]
i = 0
while i < len(line):
  if prev == line[i]:
    i += 1
    continue
  elif prev < line[i]:
    for j in range(i,len(line)):
      if line[j] < prev:
        count+=1
        i = j
        break
      prev = line[j]
  elif prev > line[i]:
    for j in range(i,len(line)):
      if line[j] > prev:
        count += 1
        i = j
        break
      prev = line[j]
  prev = line[i]
  i+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(1)
elif N == 2:
    print(1)
else:
    cnt = 0
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            A[i] = 0
            cnt += 1

    for _ in range(cnt):
        A.remove(0)
    #print(A)

    i = 1
    ans = 1
    n = len(A)
    while i < n - 1:
        if A[i-1] < A[i] < A[i+1] or A[i-1] > A[i] > A[i+1]:
            pass
        else:
            i += 1
            ans += 1
        i += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(1)
elif N == 2:
    print(1)
else:
    cnt = 0
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            A[i] = 0
            cnt += 1

    for _ in range(cnt):
        A.remove(0)
    #print(A)

    i = 1
    ans = 1
    while i < len(A) - 1:
        if A[i-1] < A[i] < A[i+1] or A[i-1] > A[i] > A[i+1]:
            pass
        else:
            i += 1
            ans += 1
        i += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(1)
elif N == 2:
    print(1)
else:
    cnt = 0
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            A[i] = '#'
            cnt += 1

    for _ in range(cnt):
        A.remove('#')
    #print(A)

    i = 1
    ans = 1
    while i < len(A) - 1:
        if A[i-1] < A[i] < A[i+1] or A[i-1] > A[i] > A[i+1]:
            pass
        else:
            i += 1
            ans += 1
        i += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
f=0
fnew=0
A=list(map(int,input().split()))
def flag(n1,n2,f):
 if n1>n2:
  return -1
 elif n1<n2:
  return 1
 else:
  return f
cnt=0
l=[]
i=0
while i<N:
 l.append(A[i])
 if (l[0]+l[len(l)-1])!=(max(l)+min(l)):
  cnt=cnt+1
  l=[]
  i=i-1
 i=i+1
print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
count=1
size=1
p=list(map(int,input().split()))
q=[p[0]]
for i in range (1,N):
  if p[i]!=p[i-1]:
    q.append(p[i])
    size+=1
j=0
while True:
  if j>=size-2:
    break
  while (q[j]-q[j+1])*(q[j+1]-q[j+2])>=0:
    if j>=size-2:
      break
      j+=1    
  count+=1
  j+=2
print(count)

Submission status: Time Limit Exceeded

Solution code:
def my_sign(n):
    return (n > 0) - (n < 0)
def kugiri(cnt, lst):
    if len(lst) <= 1:
        return cnt
    else:
        pm = lst[0]
        i = 1
        fl = 0
        while i < len(lst):
            if pm == lst[i]:
                i += 1
                continue
            else:
                fl = 1
                break
        if fl == 1:
            new_lst = []
            for j in range(i + 1, len(lst)):
                new_lst.append(lst[j])
            return kugiri(cnt + 1, new_lst)
        else:
            return cnt

N = int(input())
A_lst = [int(x) for x in input().split()]
cnt = 1
if N == 1:
    pass
else:
    S_lst = []
    for i in range(1, N):
        S_lst.append(my_sign(A_lst[i] - A_lst[i - 1]))
    for i in range(len(S_lst)):
        if i == 0 and S_lst[i] == 0:
            for j in range(len(S_lst)):
                if not S_lst[j] == 0:
                    S_lst[i] = S_lst[j]
        elif S_lst[i] == 0:
            S_lst[i] = S_lst[i - 1]
    cnt = kugiri(cnt, S_lst)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
i = 1
ans = 1
while(i<=n-2):
  if (a[i]-a[i-1]>=0) and (a[i+1]-a[i]>=0) or (a[i]-a[i-1]<=0) and (a[i+1]-a[i]<=0):
    continue
  else:
    ans += 1
    i += 1
  i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
idx = 0
count = 0
for i in range(n):
  if idx >= n:
    break
  for j in range(n, 0, -1):
    if a[idx:j] == sorted(a[idx:j]) or a[idx:j] == sorted(a[idx:j], reverse=True):
      idx += len(a[idx:j])
      count += 1
      break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
idx = 0
count = 0
for i in range(n):
  if idx == n:
    break
  for j in range(n, 0, -1):
    if a[idx:j] == sorted(a[idx:j]) or a[idx:j] == sorted(a[idx:j], reverse=True):
      idx += len(a[idx:j])
      count += 1
      break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split())) + ["a"]
t = len(a)
cnt = 0
cur = 0
while t > 2:
  l,r = 0,1
  while a[r] != "a" and a[r] == a[l]:
    r += 1
  if a[r] == "a":
    print(cnt+1)
    exit()
  d = a[r]-a[l]
  while a[r+1] != "a" and (a[r+1]-a[r])*d>=0:
    r += 1
  cnt += 1
  d = 0
  a = a[r+1:]
  t -= r+1
if a[0] != "a":
  cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split())) + ["a"]
t = len(a)
cnt = 0
cur = 0
while t > 2:
  l,r = 0,1
  while a[r] != "a" and a[r] == a[l]:
    r += 1
  if a[r] == "a":
    print(cnt+1)
    exit()
  d = a[r]-a[l]
  while a[r+1] != "a" and (a[r+1]-a[r])*d>=0:
    r += 1
  cnt += 1
  d = 0
  a = a[r+1:]
  t -= r+1
if a[0] != "a":
  cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

li = []
li_2 = []
li_3 = []
count = 0
for i in A:
    li.append(i)
    li_2.append(i)
    li_3.append(i)
    li_2.sort()
    li_3.sort(reverse=True)
    if li != li_2 and li != li_3:
        count += 1
        li = [i]
        li_2 = [i]
        li_3 = [i]

print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

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

b = [A[i+1]-A[i] for i in range(N-1)]

for i in range(b.count(0)):
    b.remove(0)

b = [0<b_i for b_i in b]

b = [len(list(v)) for k, v in groupby(b)]

# print(b)
if len(b) <= 1:
    print(1)
    exit()

c = 2
can_remove = True
for b_i in b[1:-1]:
    if b_i == 1 and can_remove:
        can_remove = False
    else:
        c += 1
        can_remove = True

print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))

ans = 0
while len(A):
    for i in range(len(A)-2):
        if (A[i+2]-A[i+1]>0)!=(A[i+1]-A[i]>0) and A[i+2]-A[i+1]!=0 and A[i+1]-A[i]!=0:
            A = A[i+2:]
            ans += 1
            break
    else:
        break

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
res = 1
flag = 0
B = []
for i in range(len(A)-1):
    B.append(A[i+1]-A[i])
while flag == 0:
    for i in range(len(B)-1):
        if B[i]*B[i+1]<0:
            A = A[i+2:]
            B = B[i+2:]
            res += 1
            break
    else:
        flag =1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
res = 1
flag = 0
while flag == 0:
    B = []
    for i in range(len(A)-1):
        B.append(A[i+1]-A[i])
    for i in range(len(B)-1):
        if B[i]*B[i+1]<0:
            A = A[i+2:]
            res += 1
            break
    else:
        flag =1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if count == 1:
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0
                
        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if(count == 1):
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0
                
        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if(count == 1):
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0


        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        if(count == 0):
            prev = tmp
            count += 1
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1

        if prev < tmp and div == -1:
            ans += 1
            div = 0
        elif prev > tmp and div == 1:
            ans += 1
            div = 0

        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0

    #pdb.set_trace()
    for tmp in array:
        if(count == 0):
            prev = tmp
            count = 1
            continue

        if prev < tmp and div == -1:
            ans += 1
            div = 0
            prev = tmp
            continue
        elif prev > tmp and div == 1:
            ans += 1
            div = 0
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1

        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[];c=1;d=[]
for i in range(1,n):
  b.append(a[i]-a[i-1])
for j in range(1,n-1):
  if b[j]*b[j-1]<0 and j-1 not in d:
    c+=1
    d.append(j)
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
answer = 0
while len(a)>2:
	if a[0]<=a[1]<=a[2] or a[0]>=a[1]>=a[2]:
		a = a[1:]
	else:
		answer += 1
		a = a[2:]
if a != []: answer+=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def cutter(nums):
    if len(nums) < 2:
        return []
    
    for i in xrange(1, len(nums)):
        if int(nums[i]) != int(nums[i-1]):
            pos = i
            flag = int(nums[i]) > int(nums[i-1])  # is asc?
            # print flag
            break
    else:
        return []

    for i in xrange(pos, len(nums)):

        if flag:
            if int(nums[i]) < int(nums[i-1]):
                return nums[i:]
        else:
            if int(nums[i]) > int(nums[i-1]):
                return nums[i:]
    return []


n = int(raw_input())
arr = raw_input().split()
if n < 2:
    print n
else:
    count = 0
    while arr:
        # print arr
        count += 1
        arr = cutter(arr)

    print count

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))

array = 0
i = 1
if n == 1:
    print("1")
else:
    while i <= n:
        if i == n:
            array += 1
            break
        if l[i] == l[i-1]:
            i += 1
            continue
        elif l[i] >= l[i-1]:
            while l[i] >= l[i-1]:
                if i == n-1:
                    break
                i += 1
            else:
                array += 1
                i += 1
                continue
        elif l[i] <= l[i-1]:
            while l[i] <= l[i-1]:
                if i == n-1:
                    break
                i += 1
            else:
                array += 1
                i += 1
                continue
    print(array)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(x) for x in input().strip().split()]

array = 0
i = 1
if n == 1:
    print("1")
else:
    while i <= n:
        if i == n:
            array += 1
            break
        if l[i] == l[i-1]:
            i += 1
            continue
        elif l[i] >= l[i-1]:
            while l[i] >= l[i-1]:
                if i == n-1:
                    break
                i += 1
            else:
                array += 1
                i += 1
                continue
        elif l[i] <= l[i-1]:
            while l[i] <= l[i-1]:
                if i == n-1:
                    break
                i += 1
            else:
                array += 1
                i += 1
                continue
    print(array)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0
trend = ""

for i in range(N):
	B.append(A[i])
	if len(B) == 2 or trend == "neutral":
		if min(B) == max(B):
			trend = "neutral"
		elif A[i] == max(B):
			trend = "up"
		elif A[i] == min(B):
			trend = "down"
	elif len(B) > 2:
		if trend == "up" and A[i] != max(B):
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] != min(B):
			cut += 1
			B = [A[i]]
print(cut + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0
trend = ""

for i in range(N):
	B.append(A[i])
	if len(B) == 2 or trend == "neutral":
		if min(B) == max(B):
			trend = "neutral"
		elif B == sorted(B):
			trend = "up"
		elif B == sorted(B, reverse = True):
			trend = "down"
	elif len(B) > 2:
		if trend == "up" and A[i] != max(B):
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] != min(B):
			cut += 1
			B = [A[i]]
print(cut + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0

for i in range(N):
	B.append(A[i])
	if B != sorted(B) and B != sorted(B, reverse = True):
		B = [A[i]]
		cut += 1
		
print(cut + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()

c = 1
i = 1
while i <= N-2:
	if int(A[i])-int(A[i-1]) > 0:
		if int(A[i+1])-int(A[i]) < 0:
			c += 1
			i += 2
		elif int(A[i+1])-int(A[i]) > 0:
			i += 1
		else:
			while int(A[i])-int(A[i-1]) == 0:
				i += 1
			if int(A[i])-int(A[i-1]) < 0:
				c += 1
				i += 2
	elif int(A[i])-int(A[i-1]) < 0:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			while int(A[i])-int(A[i-1]) == 0:
				i += 1
			if int(A[i])-int(A[i-1]) > 0:
				c += 1
				i += 2
	else:
		i += 1

 
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))

ENDED = 0
FIRST = 1
UP = 2
DOWN = 3
EVEN = 4

flg = ENDED
ret = 0
bfr = None

i = 0
while i < n:
    a_ = a[i]
    if flg == ENDED:
        ret += 1
        flg = FIRST
        i += 1
    elif flg == FIRST:
        if a_ > bfr:
            flg = UP
        elif a_ == bfr:
            flg = EVEN
        elif a_ < bfr:
            flg = DOWN
        i += 1
    elif flg == UP:
        if a_ < bfr:
            flg = ENDED
        else:
            i += 1
    elif flg == EVEN:
        if a_ > bfr:
            flg = UP
        elif a_ < bfr:
            flg = DOWN
    elif flg == DOWN:
        if a_ > bfr:
            flg = ENDED
        else:
            i += 1
    
    bfr = a_
        
print(ret)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
state = None
cnt = 1
for i in range(1, n):
    if state == None:
        if a[i] > a[i-1]:
            state = 'up'
        elif a[i] < a[i-1]:
            state = 'down'
        else:
            continue
    elif state == 'up' and a[i] < a[i-1]:
        cnt += 1
        state = None
    elif state == 'down' and a[i] > a[i-1]:
        cnt += 1
        state = None
print(cnt)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())

isInc = False
isDec = False
cnt = 1
bef_a = a[0]

for ai in a:
    if isInc and bef_a > ai:
        cnt += 1
        isInc = False
    elif isDec and bef_a < ai:
        cnt += 1
        isDec = False
    elif isInc == False and isDec == False:
        if bef_a < ai:
            isInc = True
        elif bef_a > ai:
            isDec = True
    bef_a = ai
print(cnt)

Submission status: Accepted

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

# A - Sorted Arrays
import copy

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

arr = []
ans = []
# 0: どっちの可能性もある
# 1: 単調非減少(増加)
# 2: 単調非増加(減少)
status = 0

for i in range(N):
  if status == 0:
    if len(arr) > 0:
      if A[i] > arr[-1]:
        status = 1
      elif A[i] < arr[-1]:
        status = 2

    arr.append(A[i])
  elif status == 1 and A[i] >= arr[-1]:
    arr.append(A[i])
  elif status == 2 and A[i] <= arr[-1]:
    arr.append(A[i])
  else:
    ans.append(copy.copy(arr))
    arr = [A[i]]
    status = 0

if len(arr) > 0:
  ans.append(arr)

print(len(ans))

'''
for a in ans:
  print(a)
'''

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())

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

    dp = [[10 ** 9 for j in range(2)] for i in range(n)]
    dp[0][0] = 1 # increase
    dp[0][1] = 1 # decrease

    for i in range(1, n):
        if arr[i] > arr[i-1]:
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + 1)
            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
        elif arr[i] < arr[i-1]:
            dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 1
            dp[i][1] = min(dp[i-1][0] + 1, dp[i-1][1])
        else:
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1]
    # print(dp)
    print(min(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 1
	
status = 0
for i in range(N-1):
	if A[i] > A[i+1]:
		if status == 0: status = 1
		elif status == -1:
			status = 0
			cnt += 1
	elif A[i] < A[i+1]:
		if status == 0: status = -1
		elif status == 1:
			status = 0
			cnt += 1
print(cnt)

Submission status: Accepted

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

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

ans = 0
up = None
prev = None
for v in a:
    if prev == v:
        continue
    if prev is not None:
        if up is None:
            up = (prev <= v)
        else:
            if (prev <= v) != up:
                ans += 1
                up = None
    prev = v
print(ans + 1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

cnt = n
prev = a[0]
trend ='N'

for i in range(1, n):
    if a[i] > prev:
        if (trend == 'U' or trend == 'N'):
            cnt -= 1
            trend ='U'
        else:
            trend = 'N'
    if a[i] < prev:
        if (trend == 'D' or trend == 'N'):
            cnt -= 1
            trend = 'D'
        else:
            trend = 'N'
    if a[i] == prev:
        cnt -= 1
    prev = a[i]
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
nums = list(map(int, input().split()))
upper = True
lower = True
before = nums[0]
answer = 0
for i, num in enumerate(nums):
  if before < num:
    lower = False
  elif before > num:
    upper = False
  before = num
  if not upper and not lower:
    answer += 1
    upper = True
    lower = True
print(answer+1)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))

sw='n'
ans=0
for i in range(1,n):
    if sw=='u':
        if l[i-1]-l[i]<=0:
            continue
        else:
            ans+=1
            sw='n'
    elif sw=='d':
        if l[i-1]-l[i]>=0:
            continue
        else:
            ans+=1
            sw='n'
    else:
        if l[i-1]-l[i]<0:
            sw='u'
        elif l[i-1]-l[i]>0:
            sw='d'
        else:
            continue

print(ans+1)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

d = [0] * N
for i in range(1, N):
    d[i] = A[i] - A[i - 1]

l = 0
r1 = 1
r2 = 1
ans = 0
while l < N:
    while r1 < N and d[r1] >= 0:
        r1 += 1
    while r2 < N and d[r2] <= 0:
        r2 += 1
    r = max(r1, r2)
    l = r
    ans += 1
    r1 = l + 1
    r2 = l + 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
aa =list(map(int, input().split()))

list1 =[0] * n
cnt = 1  
for i in range(n-1):
  if aa[i+1] > aa[i]:
    list1[i+1] = 1
  elif aa[i+1] < aa[i]:
    list1[i+1] = -1
  elif aa[i+1] == aa[i]:    
    list1[i+1] = 0

while 1 in list1 and -1 in list1:
  del list1[:max(list1.index(1), list1.index(-1))]
  list1[0] = 0
  cnt += 1
  
print(cnt)

Submission status: Accepted

Solution code:
n = int(input()); a = list(map(int, input().split())); b = -1; x = 1
for i in range(n-1):
    if b == 0:
        if a[i] > a[i+1]: b = -1; x += 1
    elif b == 1:
        if a[i] < a[i+1]: b = -1; x += 1
    else:
        if a[i] < a[i+1]: b = 0
        elif a[i] > a[i+1]: b = 1
print(x)

Submission status: Accepted

Solution code:
n = int(input())
num_list = list(map(int, input().split()))
ans = 1
cnt_list = [0] * n
a = int()

for i in range(1,n):
    if num_list[i-1] > num_list[i]:
        cnt_list[i] = -1
    if num_list[i-1] < num_list[i]:
        cnt_list[i] = 1

while 1 in cnt_list and -1 in cnt_list:
    del cnt_list[:max(cnt_list.index(1),cnt_list.index(-1))]
    cnt_list[0] = 0
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

ans = 0
up = 0
down = 0
i=0

while (i+1)<n:
    if up == down:
        if a[i+1] > a[i]:
            up += 1
            down = 0
        elif a[i+1] < a[i]:
            up = 0
            down += 1
        else:
            up += 1
            down += 1
    elif up == 0 and down !=0:
        if a[i+1] <= a[i]:
            down += 1
        else:
            ans += 1
            down = 0
    elif down == 0 and up!= 0:
        if a[i+1] >= a[i]:
            up += 1
        else:
            ans += 1
            up = 0
    i += 1

print(ans+1)

Submission status: Accepted

Solution code:
def f(n,a):
    if n==1:
        print(1)
        exit()
    pre=a[1]-a[0]
    ans=1
    for i in range(2,n):
        if pre*(a[i]-a[i-1])<0:
            pre=0
            ans+=1
        else:
            if a[i]-a[i-1]:###
                pre=a[i]-a[i-1]
    return ans

n=int(input())
*a,=map(int,input().split())
print(f(n,a))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
i=1
up=0
down=0
while i<n:
  if up==down:
    if a[i]>a[i-1]:
      up+=1
      down=0
    elif a[i]<a[i-1]:
      down+=1
      up=0
    elif a[i]==a[i-1]:
      up+=1
      down+=1
  elif up==0 and down!=0:
    if a[i]<=a[i-1]:
      down+=1
    else:
      ans+=1
      down=0
  elif down==0 and up!=0:
    if a[i]>=a[i-1]:
      up+=1
    else:
      ans+=1
      up=0
  i+=1
print(ans+1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

up = down = 0

cur = a[0]
ans = 0
for x in a:
    if cur < x:
        up = 1
    elif cur > x:
        down = 1
    
    if up and down:
        ans += 1
        up = down = 0

    cur = x

print(ans+1)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
i = 0
while i < n:
    while i+1 < n and a[i] == a[i+1]:
        i += 1
    if i+1 < n and a[i] < a[i+1]:
        while i+1 < n and a[i] <= a[i+1]:
            i += 1
    elif i+1 < n and a[i] > a[i+1]:
        while i+1 < n and a[i] >= a[i+1]:
            i += 1
    ans += 1
    i += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def check(A,i,j):
    tmp = []
    for k in range(i,j):
        tmp.append(A[k])

    print(tmp)

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

cnt = i = 0
while True:
    flag = 0
    for j in range(i+1,N):
        if flag == 0:
            if A[i] < A[j]:
                flag = 1
            elif A[i] > A[j]:
                flag = -1
        else:
            if flag == 1:
                if A[j-1] > A[j]:
                    #check(A,i,j)
                    i = j
                    cnt += 1
                    break
            elif flag == -1:
                if A[j-1] < A[j]:
                    #check(A,i,j)
                    i = j
                    cnt += 1
                    break
    else:
        cnt += 1
        break

    if i>=N:
        break

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

ans = 1
d = 0
for i in range(1,n):
    diff = A[i] - A[i-1]
    if not d:
        d = diff
    elif d*diff < 0:
        d = 0
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
zo=0 ; mi=0 ;ans=1
for i in range(n-1):
    #print(zo,mi,i)
    if zo==mi==0:
        if A[i]==A[i+1]:
            continue
        elif A[i]>A[i+1]:
            mi=1; continue
        else:
            zo=1;continue
    if zo:
        if A[i+1]<A[i]:
            zo=0; ans+=1
    if mi and A[i]<A[i+1]:
        mi=0 ; ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

cnt = 0
if n == 1:
  print (1)
  exit()
c = 0
for i in range(n-1):
  if c == 2 and a[i+1] < a[i]:
    cnt += 1
    c = -1
  elif c == 1 and a[i+1] > a[i]:
    cnt += 1
    c = -1
  else:
    if c < 1:
      if a[i+1] > a[i]:
        c = 2
      elif a[i+1] == a[i]:
        c = 0
      else:
        c = 1
print (cnt+1)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int,input().split()))
cnt = 1
i = 0
flag = 10
while i < n-1:
    if ls[i] < ls[i+1] and flag == 10:
        flag = True
    elif ls[i] > ls[i+1] and flag == 10:
        flag = False
    if flag == True:
        if ls[i] > ls[i+1]:
            cnt += 1
            flag = 10
    elif flag == False:
        if ls[i] < ls[i+1]:
            cnt += 1
            flag = 10
    i += 1
print(cnt)