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

Solution code:
def cutter(nums):
    if len(nums) < 2:
        return []
    flag = nums[1] > nums[0]
    for i in xrange(1, len(nums)):
        if flag:
            if nums[i] < nums[i-1]:
                return nums[i:]
        else:
            if nums[i] > nums[i-1]:
                return nums[i:]
    return []
n = int(raw_input())
arr = raw_input().split()
if n < 2:
    print n
count = 0
while arr:
    count += 1
    arr = cutter(arr)


print count

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()
n = int(input_line)
input_line = sys.stdin.readline()
a = [int(v) for v in input_line.split()]


x = 1
firstChanged = False
up = False
skip = False

for i in range(1, n) :
	if skip:
		skip = False
		continue
	diff = a[i] - a[i - 1]
	if diff != 0:
		if diff > 0:
			if firstChanged:
				if not up:
					x += 1
					up = True
					skip = True
			else:
				up = True
				firstChanged = True
		else:
			if firstChanged:
				if up:
					x += 1
					up = False
					skip = True
			else:
				up = False
				firstChanged = True

if skip:
	x += 1
print(str(x))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()
n = int(input_line)
input_line = sys.stdin.readline()
a = [int(v) for v in input_line.split()]


x = 0
firstChanged = False
up = False

for i in range(n):
	if i == 0:
		continue

	diff = a[i] - a[i - 1]
	if diff != 0:
		if diff > 0:
			if firstChanged:
				if not up:
					x += 1
					up = True
			else:
				x += 1
				up = True
				firstChanged = True
		else:
			if firstChanged:
				if up:
					x += 1
					up = False
			else:
				x += 1
				up = False
				firstChanged = True
			

print(str(x))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()
n = int(input_line)
input_line = sys.stdin.readline()
a = [int(v) for v in input_line.split()]


i = 0
x = 1
diff = 0
bdiff = 1
border = False
for i in range(1, n):
	if border:
		border = False
		continue
	diff = a[i] - a[i - 1]
	if diff == 0:
		continue

	if diff * bdiff < 0:
		x += 1
		bdiff = diff
		border = True

if border:
	x += 1

print(str(x))

Submission status: Wrong Answer

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

UP = 1
DOWN = -1

state = 0
cnt = 1
last = None
for x in A:
	if last == None:
		last = x
	elif state == 0:
		if x - last > 0:
			state = UP
		elif x - last < 0:
			state = DOWN
	else:
		if (x-last) * state >= 0:
			last = x
		else:
			last = None
			state = 0
			cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def solve(N, A):
    flag = 0
    ans = 0
    for i in range(N - 1):
        if A[i] < A[i + 1]:
            if flag == -1:
                ans += 1
                flag = 0
            else:
                flag = 1

        if A[i] > A[i + 1]:
            if flag == 1:
                ans += 1
                flag = 0
            else:
                flag = -1

    return ans


def main():
    N = II()
    A = ILI()
    print(solve(N, A))
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
l = map(int, raw_input().split())
cnt = 0
idx = 0
while(idx < n):
    while(idx < n-1 and l[idx] == l[idx+1]):
        idx += 1
    if(idx >= n-1):
        cnt += 1
        break
    plus = True
    if(l[idx] > l[idx+1]):
        plus = False
    if plus:
        while(idx < n-1 and l[idx] < l[idx+1]):
            idx += 1
        cnt += 1
        if(idx >= n-1):
            break
    else:
        while(idx < n-1 and l[idx] > l[idx+1]):
            idx += 1
        cnt += 1
        if(idx >= n-1):
            break
    idx += 1
print cnt

Submission status: Wrong Answer

Solution code:
#ARC013A
import copy

n=int(raw_input())
a=map(int,raw_input().split())
b=copy.deepcopy(a)
b.insert(0,a[0])
cnt=0
ff=0
for i in xrange(n):
 if a[i]>=b[i] and ff==0:
  continue
 elif a[i]>b[i] and ff==1:
  ff=0
  cnt+=1
 if a[i]<=b[i] and ff==1:
  continue
 elif a[i]<b[i] and ff==0:
  ff=1
  cnt+=1
print cnt+1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

n=int(raw_input().strip())
arr=map(int,raw_input().split())

b=0
cnt=0

for i in xrange(n-1):
    diff=arr[i+1]-arr[i]
    if b*diff<0:
        cnt+=1
        b=0
    else:
        b=diff
print cnt+1

Submission status: Wrong Answer

Solution code:
n = int(raw_input())

a = map(int, raw_input().split())

if n==1:
    print 1

else:
    i = 0
    count1 = 0
    while i < n:
        count1 += 1
        if i == n-1:
            break
        if a[i+1] >= a[i]:
            while i < n-1 and a[i+1] >= a[i]:
                i += 1
        else:
            while i < n-1 and a[i+1] < a[i]:
                i += 1
    #    print i,  count
        i += 1
    
    i = 0
    count2 = 0
    while i < n:
        count2 += 1
        if i == n-1:
            break
        if a[i+1] > a[i]:
            while i < n-1 and a[i+1] > a[i]:
                i += 1
        else:
            while i < n-1 and a[i+1] <= a[i]:
                i += 1
    #    print i,  count
        i += 1
        
    print min(count1, count2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
flag=[False for i in range(n)]

count=0
for i in range(n-2):
    if i%2!=0:
        if (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1; flag[i]=True
for i in range(n-2):
    if i%2==0:
        if not flag[i+1] and (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1

ans=count+1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !

def compress(ls):
    ret = []
    pre_item = -1
    for item in ls:
        if item != pre_item:
            ret.append(item)
        pre_item = item
    return ret

n = int(input())
ls = list(map(int, input().split()))
cnt = 1
if len(ls) == 1:
    cnt = 1
else:
    ls = compress(ls)
    up_flag = False
    if ls[0] < ls[1]:
        up_flag = True

    pre_item = -1
    for item in ls:
        if pre_item < item:
            if up_flag:
                pass
            else:
                up_flag = True
                cnt += 1
        else:
            if up_flag:
                up_flag = False
                cnt += 1
            else:
                pass
        #print("pre_item:", pre_item, "item:", item, "cnt:", cnt)
        pre_item = item

print(cnt)

Submission status: Wrong Answer

Solution code:
a=input()
b=map(int,raw_input().split())

time=0
fug=""

for i in range(a-1):
	if b[i+1]-b[i]>0:
		if fug!="+":
			time+=1
		fug="+"
	elif b[i+1]-b[i]<0:
		if fug!="-":
			time+=1
		fug="-"

print time/2+1

Submission status: Wrong Answer

Solution code:
a=input()
b=map(int,raw_input().split())

time=0
fug=""

for i in range(a-1):
	if b[i+1]-b[i]>0:
		if fug!="+":
			time+=1
		fug="+"
	elif b[i+1]-b[i]<0:
		if fug!="-":
			time+=1
		fug="-"
	print fug

if time%2==0:
	print time/2+1
else:
	print (time+1)/2

Submission status: Wrong Answer

Solution code:
a=input()
b=map(int,raw_input().split())

time=0
fug=""

for i in range(a-1):
	if b[i+1]-b[i]>0:
		if fug!="+":
			time+=1
		fug="+"
	elif b[i+1]-b[i]<0:
		if fug!="-":
			time+=1
		fug="-"
	print fug

if time%2==0:
	print time/2+1
else:
	print time/2+1

Submission status: Wrong Answer

Solution code:
a=input()
b=map(int,raw_input().split())

time=0
fug=""

for i in range(a-1):
	if b[i+1]-b[i]>0:
		if fug!="+":
			time+=1
		fug="+"
	elif b[i+1]-b[i]<0:
		if fug!="-":
			time+=1
		fug="-"

if time%2==0:
	print time/2+1
else:
	print time/2+2

Submission status: Wrong Answer

Solution code:
a=input()
b=map(int,raw_input().split())

lon=1
ans=1

for i in b:
	if lon==1:
		lon+=1
		pre=i
	elif lon==2:
		if pre<i:
			ori="inc"
		elif pre>i:
			ori="dec"
		else:
			ori="equal"
		pre=i
		lon+=1
	else:
		if pre<i:
			if ori=="inc":
				lon+=1
				pre=i
			elif ori=="dec":
				ans+=1
				lon=2
				pre=i
			else:
				if pre<i:
					ori="inc"
				elif pre>i:
					ori="dec"
				else:
					ori="equal"
				pre=i
				lon+=1
		elif pre>i:
			if ori=="inc":
				ans+=1
				lon=2
				pre=i
			elif ori=="dec":
				lon=+1
				pre=i
			else:
				if pre<i:
					ori="inc"
				elif pre>i:
					ori="dec"
				else:
					ori="equal"
				pre=i
				lon+=1
		else:
			lon+=1
			pre=i

print ans

Submission status: Wrong Answer

Solution code:
def comp(X, Y):
    if X == Y:
        ret = 0
    elif X < Y:
        ret = 1
    else:
        ret = 2

    return ret


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

div_Count = 1
before_mode = -1

for i in range(N-1):
    current_mode = comp(A[i], A[i+1])

    if before_mode == -1:
        before_mode = current_mode
    else:
        if before_mode == 0 or current_mode == 0:
            before_mode = current_mode
        elif before_mode == current_mode:
            before_mode = current_mode
        else:
            div_Count += 1
            before_mode = -1


print(div_Count)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
if n==1:
    print 1
    exit()
a=map(int,raw_input().split())
cnt=0
i=0
f=0
while i<n-1:
    if a[i]==a[i+1]:
        f=1
        i+=1
        continue
    elif a[i]<a[i+1]:
        while i<n-1 and a[i]<=a[i+1]:
            i+=1
    else:
        while i<n-1 and a[i]>=a[i+1]:
            i+=1
    f=0
    cnt+=1
    i+=1
if f==1:cnt+=1
print cnt

Submission status: Wrong Answer

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

d = 0
c = 1
i = 1

while i <= N-2:
	if int(A[i])-int(A[i-1]) == 0:
		del A[i-1]
		i += 1
		d += 1
		N -= 1
	else:
		i += 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
		else:
			i += 1
	else:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			i += 1
 
print(c)

Submission status: Wrong Answer

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


l = [[] for i in range(N)]
c = 0

s = 0
t = a[0]

for i in a[1:]:
	if t > i:
		l[s].append((c))
		s = c+1
	c += 1
	t = i
else:
	l[s].append((c))

c = 0

s = 0
t = a[0]

for i in a[1:]:
	if t < i:
		l[s].append((c))
		s = c+1
	c += 1
	t = i
else:
	l[s].append((c))

l[0] = max(l[0])
for i in range(1,N):
	l[i].append(-1)
for i in range(1,N):
	
	if i!=N-1:
		l[i+1].append(-1)
		l[i] = max(l[i-1],max(l[i]),max(l[i+1]))
	else:
		l[i] = max(l[i-1],max(l[i]))


now = 0
res = 0

while now<N-1:
	now = l[now]	
	res+=1

print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=input().split()
#print(type(a),a)

h = []#0:不明1:増加2:減少(配列の変化の方向)
h1=[] #最終的に分ける配列の数

for i in range(n-1):
  if a[i] == a[i+1]:
    h.append(0)
  elif a[i] < a[i+1]:
    h.append(1)
  else:
    h.append(2)

#print(h)
#print(len(h))


for i in range(len(h)-1):
  if h[i] ==1 and h[i+1] ==2:
    h1.append(1)
  elif h[i] ==2 and h[i+1] ==1:
    h1.append(1)

ans = sum(h1)
print(ans)

Submission status: Wrong Answer

Solution code:
N = map(int,raw_input().split())
N=N[0]
A = map(int,raw_input().split())

r = A[0]
count = 0
for i in range(N-1):
    _r = A[i+1] - A[i]

    if r*_r<0:
        count += 1
        r = _r
 
print(count+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
flag=[False for i in range(n)]

count=0
for i in range(n-2):
    if i%2==0:
        if (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1; flag[i]=True
    else:
        if not flag[i-1] and (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1

ans=count+1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
flag=[False for i in range(n)]

count=0
for i in range(n-2):
    if i%2==0:
        if (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1; flag[i]=True
    else:
        if (a[i+1]-a[i])*(a[i+2]-a[i+1])<0: count+=1
        if flag[i-1]: count-=1

ans=count+1
print(ans)

Submission status: Wrong Answer

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

pv = A.pop(0)
sign = 0
count = 0
while len(A) > 0:
    v = A.pop(0)
    if sign * (v - pv) < 0:
        count += 1
        sign = 0
        pv = v
        continue
    if v != 0:
        sign = v - pv
    pv = v
print(count+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
tmp = A[0]
state = 0
M = 1
for i in range(N):
    if state == 0:
        if A[i] >= tmp :
            state = 1
        else:
            state = 2
    elif state == 1:
        if A[i] < tmp :
            state = 0
            M += 1
    else:
        if A[i] > tmp :
            state = 0
            M += 1
    tmp = A[i]
print (M)

Submission status: Wrong Answer

Solution code:
N=input()
s=[int (i) for i in input().split()]
a=0
for i in range(2,len(s)):
    if (s[i-1]-s[i])*(s[i-2]-s[i-1])<0:
        i=i+1
        a=a+1
    i=i+1
print(a)

Submission status: Wrong Answer

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
		else:
			i += 1
	elif int(A[i])-int(A[i-1]) < 0:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			i += 1
	else:
		c += 1
		i += 2

print(c)

Submission status: Wrong Answer

Solution code:
N=input()
s=[int (i) for i in input().split()]
a=0
for i in range(2,len(s)):
    if (s[i-1]-s[i])*(s[i-2]-s[i-1])<0:
        print(i)
        i=i+1
        a=a+1
        print(i)
    i=i+1
print(a)

Submission status: Wrong Answer

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

import sys
import os
import math


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

def remove_dup(A):
    B = []
    current = None
    for a in A:
        if current != a:
            B.append(a)
            current = a
    return B

# 同じ数字が続いたら除去
B = remove_dup(A)

# Diff
D = []
for i in range(len(B)-1):
    diff = B[i+1] - B[i]
    if diff > 0:
        D.append(1)
    else:
        D.append(-1)
#print(D)

# また重複除去
E = remove_dup(D)
#print(E)

num = math.ceil(len(E)/2)
print(num + 1)

Submission status: Wrong Answer

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
		else:
			i += 1
	else:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			i += 1

print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

n=int(raw_input().strip())
arr=map(int,raw_input().split())

diff_arr=[arr[i+1]-arr[i] for i in xrange(n-1)]
skip=-1
cnt=0
for i in xrange(n-2):
    if i==skip:
        continue
    if diff_arr[i+1]*diff_arr[i]<0:
        cnt+=1
        skip=i+1
print cnt+1

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
cnt=0
i=0
f=0
while i<n-1:
    if a[i]==a[i+1]:
        f=1
        i+=1
        continue
    elif a[i]<a[i+1]:
        while i<n-1 and a[i]<=a[i+1]:
            i+=1
    else:
        while i<n-1 and a[i]>=a[i+1]:
            i+=1
    f=0
    cnt+=1
    i+=1
if f==1:cnt+=1
print cnt

Submission status: Wrong Answer

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

import sys
import os
import math


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

# 同じ数字が続いたら除去
B = []
current = None
for a in A:
    if current != a:
        B.append(a)
        current = a

# Diff
D = []
for i in range(len(B)-1):
    diff = B[i+1] - B[i]
    if diff > 0:
        D.append(1)
    else:
        D.append(-1)
#print(D)

# 折れ線で分割する
change_num = 0
for i in range(len(D)-1):
    if D[i] != D[i+1]:
        change_num += 1

split_num = math.ceil(change_num / 2)
print(split_num + 1)

Submission status: Wrong Answer

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

l = [[] for i in range(N)]
c = 0

s = 0
t = a[0]

for i in a[1:]:
	if t > i:
		l[s].append((s,c))
		s = c+1
	c += 1
	t = i
else:
	l[s].append((s,c))

c = 0

s = 0
t = a[0]

for i in a[1:]:
	if t < i:
		l[s].append((s,c))
		s = c+1
	c += 1
	t = i
else:
	l[s].append((s,c))

for i in range(N):
	l[i].sort()

now = 0
res = 0
while now < N:
	now = l[now][-1][1]+1
	res+=1

print(res)

Submission status: Wrong Answer

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

count = 1
ind = 1

def check_inc_dec(i):
    if i == n-1:
        return True
    if a[i] < a[i+1]:
        return True # 増加
    else:
        return False # 減少

flag = check_inc_dec(0)

while ind < n:
    if flag == True and a[ind] < a[ind-1]:
        count += 1
        flag = check_inc_dec(ind) # つぎにの連蔵した列は増加か減少かを確かめる
    elif flag == False and a[ind] > a[ind-1]:
        count += 1
        flag = check_inc_dec(ind)
    ind += 1

print(count)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
B=[int(x) for x in raw_input().split()]
A=[-1]
for b in B:
    if b != A[-1]:
        A.append(b)
N=len(A)
i=1
ans=1
while i<N-1:
    if (A[i]-A[i-1])*(A[i+1]-A[i])<0:
        ans+=1
        i+=1
    i+=1
print ans

Submission status: Wrong Answer

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

import sys
import os
import math


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

# 同じ数字が続いたら除去
B = []
current = None
for a in A:
    if current != a:
        B.append(a)
        current = a

# Diff
D = []
for i in range(len(B)-1):
    diff = B[i+1] - B[i]
    D.append(diff)
#print(D)

# 折れ線で分割する
change_num = 0
for i in range(len(D)-1):
    if D[i] != D[i+1]:
        change_num += 1

split_num = math.ceil(change_num / 2)
print(split_num + 1)

Submission status: Wrong Answer

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

count = 0
a = 0
b = 0
for i in range(len(N)-1):
    if N[i+1] - N[i] > 0:
        b = 1
    elif N[i+1] - N[i] < 0:
        b = -1
    else:
        b = 0
        
    if a == 0:
        a = b  
    elif a == b:
        pass
    elif a == b * (-1):
        count += 1
    else:
        pass

print(count+1)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
A+=[A[-1]]
B=[]
i=1
ans=1
while i<N:
    if (A[i]-A[i-1])*(A[i+1]-A[i])<0:
        ans+=1
        i+=1
    i+=1
print ans

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[]
endflag=False
ans=1
if N>2:
	for i in range(N-1):
		if A[i]<A[i+1]:
			B.append(1)
		elif A[i]==A[i+1]:
			B.append(0)
		else:
			B.append(-1)
	count=0
	while B[count]==0:
		count+=1
		if count>N-1:
			endflag=True
			break
	print(A)
	print(B)
	if not endflag:
		mode=B[count]
		
		while count<N-1:
			if B[count]+mode==0:
				print(count,mode)
				ans+=1
				if count==N-2:
					break
				while B[count+1]==0:
					count+=1
					if count>N-1:
						endflag=True
						break
				mode=B[count+1]
			count+=1
			if endflag:
				break
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
B=[]
i=1
ans=1
while i<len(A)-1:
    if (A[i]-A[i-1])*(A[i+1]-A[i])<0:
        ans+=1
        i+=1
    i+=1
print ans

Submission status: Wrong Answer

Solution code:

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

num_split = 1
diff = None
len_A_list = len(A_list)

for i in range(len_A_list-1):
    if diff == None:
        diff = A_list[i+1] - A_list[i]

    if A_list[i+1] - A_list[i] == diff:
        continue

    num_split += 1
    diff = None

print(num_split)

Submission status: Wrong Answer

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

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

dp[0][0] = 1
dp[1][0] = 1
for i in range(1, N):
    if As[i - 1] < As[i]:
        dp[0][i] = min(dp[0][i - 1], dp[1][i - 1] + 1)
        dp[1][i] = min(dp[0][i - 1] + 1, dp[1][i - 1] + 1)
    elif As[i - 1] > As[i]:
        dp[0][i] = min(dp[0][i - 1] + 1, dp[1][i - 1] + 1)
        dp[1][i] = min(dp[0][i - 1] + 1, dp[1][i - 1])
    else:
        dp[0][i] = min(dp[0][i - 1], dp[1][i - 1])
        dp[1][i] = min(dp[0][i - 1], dp[1][i - 1])

ans = min(dp[0][N - 1], dp[1][N - 1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
cnt=0
i=0
while i<n-1:
    if a[i]==a[i+1]:
        i+=1
        continue
    elif a[i]<a[i+1]:
        cnt+=1
        while i<n-1 and a[i]<=a[i+1]:
            i+=1
    else:
        cnt+=1
        while i<n-1 and a[i]>=a[i+1]:
            i+=1
    i+=1
print max(cnt,1)

Submission status: Wrong Answer

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

ret = 1

i = 0
while i < n-2:
    if (a[i] > a[i+1] and a[i+1] < a[i+2]) or (a[i] < a[i+1] and a[i+1] > a[i+2]):
        ret += 1
        i += 2
    else:
        i += 1
        
print(ret)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())

a = map(int, raw_input().split())

i = 0
count1 = 0
while i < n:
    count1 += 1
    if i == n-1:
        break
    if a[i+1] >= a[i]:
        while i < n-1 and a[i+1] >= a[i]:
            i += 1
    else:
        while i < n-1 and a[i+1] < a[i]:
            i += 1
#    print i,  count
    i += 1

i = 0
count2 = 0
while i < n:
    count2 += 1
    if i == n-1:
        break
    if a[i+1] > a[i]:
        while i < n-1 and a[i+1] > a[i]:
            i += 1
    else:
        while i < n-1 and a[i+1] <= a[i]:
            i += 1
#    print i,  count
    i += 1

    
print min(count1, count2)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
cnt=0
i=0
while i<n-1:
    if a[i]==a[i+1]:
        i+=1
        continue
    elif a[i]<a[i+1]:
        cnt+=1
        while i<n-1 and a[i]<=a[i+1]:
            i+=1
        continue
    else:
        cnt+=1
        while i<n-1 and a[i]>=a[i+1]:
            i+=1
    i+=1
print max(cnt,1)

Submission status: Wrong Answer

Solution code:

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

num_split = 1
is_increase = None
len_A_list = len(A_list)

for i in range(len_A_list-1):
    if is_increase == None:
        if A_list[i] < A_list[i+1]:
            is_increase = True
        else:
            is_increase = False

    if is_increase and A_list[i] < A_list[i+1]:
        continue
    if (not is_increase) and A_list[i] > A_list[i+1]:
        continue

    num_split += 1
    is_increase = None

print(num_split)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
B=[]
i=1
ans=1
while i<len(A)-1:
    if (A[i]-A[i-1])*(A[i+1]-A[i])<0:
        ans+=1
        i+=1
    i+=1
print ans

Submission status: Wrong Answer

Solution code:
N = input()
A = map(int, raw_input().split())
p = 0
ans = 1
for i in range(1, N):
    if p*(A[i]-A[i-1])<0:
        ans += 1
        p = 0
    else:
        p = A[i]-A[i-1]
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

if N == 1:
    print(1)
    quit()

tend = 1 if A[0] < A[1] else -1
count = 1
prev = A[1]

for a in A[2:]:
    if prev < a and tend < 0:
        tend = 0
        count += 1
    elif prev > a and tend > 0:
        tend = 0
        count += 1
    elif tend == 0:
        if prev < a:
            tend = 1
        elif prev > a:
            tend = -1
        else:
            tend = 0

    prev = a

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
array = list(map(int, input().split()))
isHead = True
isIncrease = False
count = 1
for i in range(1, n):
    if(isHead):
        isHead = False
        if(array[i] > array[i-1]):
            isIncrease = True
        elif(array[i] < array[i-1]):
            isIncrease = False
    else:
        if(isIncrease):
            if(array[i] < array[i-1]):
                count += 1
                isHead = True
                continue
        else:
            if(array[i] > array[i-1]):
                count += 1
                isHead = True
                continue
print(count)

Submission status: Wrong Answer

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

N = int(raw_input())
A = map(int, raw_input().split())

tmp1 = 1
i = 0
while i < N - 2:
    if A[i] <= A[i + 1] <= A[i + 2]:
        i += 1
    elif A[i] >= A[i + 1] >= A[i + 2]:
        i += 1
    else:
        tmp1 += 1
        i += 2

tmp2 = 1
i = N - 3 
while 0 <= i:
    if A[i] <= A[i + 1] <= A[i + 2]:
        i -= 1
    elif A[i] >= A[i + 1] >= A[i + 2]:
        i -= 1
    else:
        tmp2 += 1
        i -= 2

print min(tmp1, tmp2)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
 
atmp=100000000000000000
for k in [0,1]:
    mode=k
    ans=1
    for i in range(1,N):
        if mode:
            if A[i]<A[i-1]:
                mode=0
                ans+=1
        else:
            if A[i]>A[i-1]:
                mode=1
                ans+=1
    atmp=min(atmp,ans)
print atmp

Submission status: Wrong Answer

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

c = 1

t = a[0]
for i in a[1:]:
	if t > i:
		c += 1
	t = i

print(c)

Submission status: Wrong Answer

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

N = int(raw_input())
A = map(int, raw_input().split())

ans = 1
i = 0
while i < N - 2:
    if A[i] <= A[i + 1] <= A[i + 2]:
        i += 1
    elif A[i] >= A[i + 1] >= A[i + 2]:
        i += 1
    else:
        ans += 1
        i += 2


print ans

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = [int(c) for c in input().strip().split()]
ans = 1

i = 0
while i < n - 2:
    a, b, c = xs[i:i+3]
    if (b - a) * (c - b) < 0:
        ans += 1
        i += 1
    i += 1
print(ans)

Submission status: Time Limit Exceeded

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

list1 =[0] * n
cnt = 0  
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:
  if list1[1] == 1:
    for i in range(len(list1)):
      if list1[i] == -1:
        cnt += 1
        list1[i] = 0
        list1 = list1[i:]
        
        break
        
  elif list1[1] == -1:
    for i in range(len(list1)):
      if list1[i] == 1:
        cnt += 1
        list1[i] = 0
        list1 = list1[i:]
        
        break
        
  elif list1[1] == 0:
    for i in range(len(list1)):
      if list1[i] == 1 or list1[i] == -1:
        cnt += 1
        list1[i] = 0
        list1 = list1[i:]
       
        break
  
print(cnt+1)

Submission status: Time Limit Exceeded

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

ans = {}
cnt = 0
while A != []:
    if A[0] <= A[-1]:
        for i in range(1, len(A) + 1):
            if sorted(A[:i]) == A[:i] or sorted(A[:i], reverse = True) == A[:i]:
                ans[cnt] = A[:i]
                dummy_A = A[i:]
        A = dummy_A
        cnt += 1
    else:
        for i in range(len(A)-1, -1, -1):
            if sorted(A[i:]) == A[i:] or sorted(A[i:], reverse = True) == A[i:]:
                ans[cnt] = A[i:]
                dummy_A = A[:i]
        A = dummy_A
        cnt += 1

print(len(list(ans.values())))

Submission status: Time Limit Exceeded

Solution code:

def sign(x):
    return (x > 0) - (x < 0)


def main():
    _ = int(input())
    a = map(int, input().split())
    ans = []
    arr = []
    for an in a:
        if len(arr) < 2:
            arr.append(an)
        else:
            state = sum([el - arr[i] for i, el in enumerate(arr[1:])])
            if state == 0:
                arr.append(an)
            else:
                current = an - arr[-1]
                if current == 0 or sign(state) == sign(current):
                    arr.append(an)
                else:
                    ans.append(arr)
                    arr = [an]
    ans.append(arr)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

while len(A)>1:
    if A[0]==A[1]:
        A=A[1:]
    else:
        res=(A[1]>A[0])
        for i in range(len(A)-1):
            if (A[i+1]<A[i] and res) or (A[i+1]>A[i] and not res):
                A=A[i+1:]
                counter+=1
                break


print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
cnt = 1
list = [a[0]]

for i in range(1,n):
    list.append(a[i])
    sort = sorted(list)
    if sort == list :
        continue
    sort_reverse = sorted(list,reverse=True)
    if sort != list and sort_reverse != list:
        cnt += 1
        list = [a[i]]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
cnt = 1
list = [a[0]]

for i in range(1,n):
    list.append(a[i])
    sort = sorted(list)
    sort_reverse = sorted(list,reverse=True)
    if sort != list and sort_reverse != list:
        cnt += 1
        list = [a[i]]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    
    idx = 0
    ans = 0
    for i in range(len(A)):
        if idx + 1 > len(A) - 1 :
            break

        m = ""
        if A[idx] < A[idx + 1]:
            m = "+"
        elif A[idx] > A[idx + 1]:
            m = "-"
        else:
            find = False
            for j in range(idx, len(A)-1):
                if A[j] < A[j + 1]:
                    m = "+"
                    find = True
                    break
                elif A[j] > A[j + 1]:
                    m = "-"
                    find = True
                    break
            if find == False:
                print(ans + 1)
                exit()

        for j in range(idx, len(A) - 1):
            if m == "+":
                if A[j] <= A[j + 1]:
                    pass
                else:
                    idx = j + 1
                    ans += 1
                    break
            elif m == "-":
                if A[j] >= A[j + 1]:
                    pass
                else:
                    idx = j + 1
                    ans += 1
                    break

    print(ans + 1)

if __name__ == "__main__":
    main()

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)