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

Solution (Python):

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 = 1
    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()

Solution (Python):


n=int(raw_input())
a=map(int,raw_input().split())
cnt=0
ff=0
for i in xrange(1,n):
 if a[i-1]<a[i]:
  if ff<0:
   cnt+=1
   ff=0
  else:
   ff=1
 elif a[i-1]>a[i]:
  if ff>0:
   cnt+=1
   ff=0
  else:
   ff=-1
print cnt+1

Solution (Python):

N=int(input())

mozir=input()
hyo=mozir.split(' ')
A=[int(mono) for mono in hyo]


subseq_nth=0
subseq_mae=None
subseq_muki=None

for mono in A:
    if subseq_mae==None:
        subseq_nth+=1
        subseq_mae=mono

    else:
        if subseq_muki==None:
            if subseq_mae==mono:
                subseq_mae=mono

            elif subseq_mae>mono:
                
                subseq_muki=-1
                subseq_mae=mono

            else:
                subseq_muki=1
                subseq_mae=mono

                
        elif (mono - subseq_mae) * subseq_muki >= 0:
            
            
            subseq_mae=mono

        else:
            
            subseq_mae=mono
            subseq_nth+=1
            subseq_muki=None



pass

print(subseq_nth)

Solution (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
    elif b==0:
        b=diff
print cnt+1

Solution (Python):
n=input()
arr=map(int,raw_input().split())

typ=0
total=1
k=0
t=0
i=0
while i<n:
    item=arr[i]
    if t==0:
        t=item
        continue
    if t>item:
        while i<n:
            item=arr[i]
            if t>=item:
                t=item
                i=i+1
            else:
                total+=1
                break
    elif t<item:
        while i<n:
            item=arr[i]
            if t<=item:
                t=item
                i=i+1
            else:
                total+=1
                break
    if i<n:
        item=arr[i]
        t=item
    i=i+1
            
print total

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ans = 1
incr = None
for i, x in enumerate(a):
    if i==0:
        before = x
        continue
    if incr==None:
        if x > before:
            incr = 1
        elif x < before:
            incr = -1
        before = x
        continue
    if (incr==1)and(x < before):
        ans += 1
        incr = None
    elif (incr==-1)and(x > before):
        ans += 1
        incr = None
    before = x    
print(ans)

Solution (Python):
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
    if i==n-2:
        cnt+=1
        break
    i+=1
if f==1:cnt+=1
print cnt

Solution (Python):
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] < B[-2]:
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] > B[-2]:
			cut += 1
			B = [A[i]]
print(cut + 1)

Solution (Python):
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
        a = 0
    else:
        pass

print(count+1)

Solution (Python):
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
current_mode = 0

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

    if current_mode == 0:
        current_mode = current_comp
    else:
        if current_mode == 0 or current_comp == 0:
            pass
        elif current_mode != current_comp:
            div_Count += 1
            current_mode = 0
        else:
            pass

print(div_Count)

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())

result = 1
flagFirst = True
status = "same"

for i in range(len(A) - 1):
    if flagFirst:
        flagFirst = False
        if A[i] < A[i + 1]:
            status = "up"
        elif A[i] == A[i + 1]:
            status = "same"
        else:
            status = "down"
    else:
        if ((A[i] < A[i + 1]) and status == "down") or (A[i] > A[i + 1] and status == "up"):
            flagFirst = True
            result += 1
        if status == "same":
            if A[i] < A[i + 1]:
                status = "up"
            elif A[i] > A[i + 1]:
                status = "down"

print(result)

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

c = 1
i = 1

while i <= N-1:
	if int(A[i])-int(A[i-1]) == 0:
		del A[i-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)

Solution (Python):


import sys
import os
import math


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


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)


sign = None
num = 0
for i in range(len(B)-1):
    diff = B[i+1] - B[i]
    if sign is None:
        if diff > 0:
            sign = 1
        else:
            sign = -1
    else:
        if sign == 1 and diff < 0 or sign == -1 and diff > 0:
            sign = None
            num += 1
print(num + 1)

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

sign = 0
c = 0
for i in range(1,len(A)):
    dif = A[i] - A[i-1]
    if dif * sign < 0:
        c += 1
        sign = 0
        continue
    if dif != 0:
        sign = dif
print(c+1)

Solution (Python):
def read():
    return list(map(int, input().split()))

n = read()[0]

a = read()
p = a[0]
res = 0
num = 0
for i in range(1, n):
    q = a[i]
    if p > q:
        if res == 1:
            num += 1
            res = 0
        elif res == 0:
            res = -1
    elif p < q:
        if res == -1:
            num += 1
            res = 0
        elif res == 0:
            res = 1
    p = q
print(num + 1)

Solution (Python):
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
if N==1:
	print(1)
	exit()
print(res)

Solution (Python):
n = input()
a = map(int, raw_input().split())

b = []
for i in xrange(1, n):
    if a[i] - a[i-1] != 0:
        b.append(a[i] - a[i-1])
dont_mind = True
c = 1
i = 1
while i < len(b):
    prev = b[i-1]
    t = prev * b[i]
    if t >= 0:
        i += 1
        continue
    if t < 0:
        c += 1
        i += 2
        continue
    i += 1
print c

Solution (Python):
def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    plus = 0
    minus = 0
    split = 1
    i = 0
    while i < N - 1:
        if A[i] == A[i+1]:
            pass
        elif A[i] < A[i+1]:
            if minus != 0:
                split += 1
                minus = 0
            else:
                plus = 1
        elif A[i] > A[i+1]:
            if plus != 0:
                split += 1
                plus = 0
            else:
                minus = 1
        i += 1

    print(split)

main()

Solution (Python):
N = input()
A = list(map(int,input().split()))
cnt = 1
for i,a in enumerate(A):
	if i == 0:
		flag = 0
	elif flag == 0 and a == A[i - 1]:
		pass
	elif a >= A[i - 1] and flag >= 0:
		flag = 1
	elif a <= A[i - 1] and flag <= 0:
		flag = -1
	else:
		flag = 0
		cnt += 1
print(cnt)

Solution (Python):
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
        elif A[i] < tmp:
            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)

Solution (Python):
n = int(input())
array = list(map(int, input().split()))
status = 0
past = 0
count = 1
for i in range(1, n):
    past = status
    if(array[i-1] < array[i]):
        if(status == 0):
            past = 1
        status = 1
    elif(array[i-1] > array[i]):
        if (status == 0):
            past = 2
        status = 2

    if(status != past):
        count += 1
        i += 2
        past = 0
        status = 0
        continue

print(count)

Solution (Python):
n = int(input())
array = list(map(int, input().split()))
status = 0
past = 0
tail = 0
count = 1
for i in range(1, n):
    past = status
    if(array[i-1] < array[i]):
        if(status == 0):
            past = 1
        status = 1
    elif(array[i-1] > array[i]):
        if (status == 0):
            past = 2
        status = 2

    if(status != past):
        count += 1
        i += 2
        past = 0
        status = 0
        continue




print(count)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
res = 1
non_increasing = True
non_decreasing = True
for i in range(1, n):
    non_decreasing &= a[i-1] <= a[i]
    non_increasing &= a[i-1] >= a[i]
    if not (non_increasing or non_decreasing):
        res += 1
        non_increasing = True
        non_decreasing = True
print(res)

Solution (Python):

n=int(input())
data=list(map(int,input().split()))
index=0
ans=1
v=0
while index<len(data):
    if index+1<len(data):
        if data[index]==data[index+1]:
            pass
        elif data[index]<data[index+1]:
            if v==1 or v==0:
                v=1
            else:
                ans+=1
                v=0
        else:
            if v==-1 or v==0:
                v=-1
            else:
                ans+=1
                v=0
    index+=1
print(ans)

Solution (Python):
read = lambda: map(int, input().split())
n = int(input())
a = list(read())
cnt = 1
f = 0
for i in range(1, n):
    if a[i] > a[i - 1] and f == -1:
        f = 0
        cnt += 1
    elif a[i] < a[i - 1] and f == 1:
        f = 0
        cnt += 1
    elif a[i] > a[i - 1]:
        f = 1
    elif a[i] < a[i - 1]:
        f = -1
print(cnt)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

res = 1
increasing = True
decreasing = True

for i in range(n):
    if i > 0:
        if a[i - 1] > a[i]:
            increasing = False
        if a[i - 1] < a[i]:
            decreasing = False
    if not (increasing or decreasing):
        res += 1
        increasing = True
        decreasing = True
print(res)

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

count = 1
ind = 1

def check_inc_dec(i):
    global ind
    if i == n-1:
        return False
    if a[i] < a[i+1]:
        return True 
    elif a[i] > a[i+1]:
        return False 
    else: 
        for j in range(i+1, n):
            if a[i] < a[j]:
                ind = j
                return True
            elif a[i] > a[j]:
                ind = j
                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)

Solution (Python):

N = int(input())
A = [int(n) for n in input().split()]

tmp = []
result = 1
diff = 0

for i, a in enumerate(A):
    if len(tmp) <= 0:
        tmp.append(a)
    else:
        if tmp[-1] == a:
            pass
        elif (a - tmp[-1]) * diff < 0:
            result += 1
            diff = 0
            tmp = [a]
        else:
            diff = a - tmp[-1]
            tmp.append(a)
print(result)

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
dp = [1, 1]
p = a[0]
for x in a:
    t = min(dp)
    ndp = [t + 1, t + 1]
    if p <= x and ndp[0] > dp[0]:
        ndp[0] = dp[0]
    if p >= x and ndp[1] > dp[1]:
        ndp[1] = dp[1]
    dp = ndp
    p = x
print min(dp)

Solution (Python):
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)
A.pop(0)
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

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

split = 1
skip = True

for a in A:
    if skip == True:
        skip = not skip
        tmp = a
        zouka = 0
        continue
    if tmp == a:
        continue
    if zouka == 0:
        if a > tmp:
            zouka = 1
        else:
            zouka = -1
    elif zouka > 0:
        if a < tmp:
            split += 1
            zouka = 0
    else:
        if a > tmp:
            split += 1
            zouka = 0
    tmp = a
print(split)

Solution (Python):
N = int(input())

res = 0
status = 0
A = list(map(int, input().split()))
pre = A[0]
for i in range(1, N):
    if status == 0:
        if pre < A[i]:
            status = 1
            res += 1
        elif pre > A[i]:
            status = 2
            res += 1
    elif (status == 1 and pre > A[i]) or (status == 2 and pre < A[i]):
        status = 0
    pre = A[i]

if status == 0:
    res += 1

print (str(res))

Solution (Python):
import math

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

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

for i in range(len_A_list-1):
    if sign == None:
        if A_list[i+1] - A_list[i] == 0:
            continue
        sign = (A_list[i+1] - A_list[i]) / math.fabs(A_list[i+1] - A_list[i])

    if (A_list[i+1] - A_list[i]) *  sign >= 0:
        continue

    num_split += 1
    sign = None

print(num_split)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
t = A[0]
s = -1
ans = 1
for i, a in enumerate(A):
	if s > 0:
		if a < t:
			ans += 1
			s = -1
	elif s < 0:
		if t < a:
			s = 1
		elif t > a:
			s = 0
	else:
		if a > t:
			ans += 1
			s = -1
	t = a
print(ans)

Solution (Python):
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] + 1)
        dp[1][i] = min(dp[0][i - 1] + 1, dp[1][i - 1])

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

Solution (Python):
n = int(input())
A = input().split(" ")

r = 1
p = int(A[0])
status = 0

for a in A[1:]:
    a=int(a)
    if status == 0:
        status = a-p
    elif status < 0:
        if a-p > 0:
            r = r + 1
            status = 0
    elif status >0:
        if a-p < 0:
            r = r + 1
            status = 0
    p=a

print(r)

Solution (Python):
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
	
	
	if not endflag:
		mode=B[count]
		
		while count<N-1:
			if B[count]+mode==0:
				
				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)

Solution (Python):

n = int(input())
a_ = list(map(int, input().split(' ')))
a = [-1]
i = 0
while  i < n:
    if a[-1] != a_[i]:
        a.append(a_[i])
    i += 1
a = a[1:]
n = len(a)

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)

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

mode = 0
count = 1

for i in range(1, N):
    d = a[i] - a[i - 1]
    if mode == 0:
        mode = d
        continue
    if d > 0:
        if mode < 0:
            count += 1
            mode = 0
    elif d < 0:
        if mode > 0:
            count += 1
            mode = 0

print(count)

Solution (Python):
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
    elif A[i]-A[i-1] != 0:
        p = A[i]-A[i-1]
print ans

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())

cnt = 0
v = None
u = True
d = True
for a in A:
    if v == None:
        v = a
        cnt += 1
    elif a > v:
        if u == False:
            cnt += 1
            u = True
            d = True
        else:
            d = False
    elif a < v:
        if d == False:
            cnt += 1
            u = True
            d = True
        else:
            u = False
    v = a
print cnt

Solution (Python):


N = int(raw_input())
A = map(int, raw_input().split())
B = [A[0]]
for ai in A[1:]:
    if B[-1] != ai:
        B.append(ai)
A = B[:]
N  = len(A)

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

Solution (Python):
import sys
import math

INF = 10**9+7

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()
def nsl(): return list(stdin.readline().strip())
def ni(): return int(stdin.readline())
def nil(): return list(map(int, stdin.readline().split()))

n = ni()
a = nil()

ans = 1
c = a[0]
fg = 0
for i in range(1, n):
    if a[i] == c:
        c = a[i]
    elif a[i] > c :
        if fg == 1 or fg == 0:
            fg = 1
            c = a[i]
        else:
            ans += 1
            c = a[i]
            fg = 0
    else:
        if fg == -1 or fg == 0:
            fg = -1
            c = a[i]
        else:
            ans += 1
            c = a[i]
            fg = 0


print(ans)

Solution (Python):
N = input()
A = map(int, raw_input().split(" "))

is_up = False
is_down = False
last_val = 0
ans = 1

for i in A:
    if last_val == 0:
        last_val = i
    elif not (is_up or is_down) and i > last_val:
        is_up = True
        last_val = i
    elif not (is_up or is_down) and i < last_val:
        is_down = True
        last_val = i
    elif(is_up and i < last_val):
        ans += 1
        is_up = False
        last_val = i
    elif(is_down and i > last_val):
        ans += 1
        is_down = False
        last_val = i
    else:
        last_val = i

print ans

Solution (Python):



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

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

if A[0] < A[1]:
    tend = 1
elif A[0] > A[1]:
    tend = -1
else:
    tend = 0

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)

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


status = 0
ans = 1
for i in range(1, N):
    if status == 0:
        if a[i - 1] < a[i]:
            status = 1
        elif a[i] < a[i - 1]:
            status = -1
    elif status == 1:
        if a[i] < a[i - 1]:
            status = 0
            ans += 1
    elif status == -1:
        if a[i - 1] < a[i]:
            status = 0
            ans += 1

print(ans)

Solution (Python):
def main():
    n = int(raw_input())
    a = [int(x) for x in raw_input().split()]
    if n == 1:
        print(1)
        return
    c = cmp(a[0], a[1])
    ans = 1
    for i in xrange(2, n):
        nc = cmp(a[i - 1], a[i])
        if nc == 0:
            continue
        if c == 0:
            c = nc
        elif nc != c:
            c = 0
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def solve():
    n = int(input())
    A = [int(i) for i in input().split()]

    flag = 0
    l = 0
    r = 0
    cnt = 0

    while r < n - 1:
        if A[r] == A[r + 1]:
            r += 1
        elif A[r] < A[r + 1]:
            if flag == 2:
                cnt += 1
                flag = 0
                l = r + 1
                r = l
            else:
                flag = 1
                r += 1
        else:
            if flag == 1:
                cnt += 1
                flag = 0
                l = r + 1
                r = l
            else:
                flag = 2
                r += 1

    cnt += 1

    print(cnt)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Solution (Python):



from random import *
from functools import reduce,partial

def readline():
    return list(map(int,input().split(' ')))

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

n = int(input())
a = readline()
f = sequence(n)
g = sequence(n)
f[0],g[0] = 1,1
for i in range(1,n):
    f[i] = min(f[i-1],g[i-1] + 1)
    g[i] = min(g[i-1],f[i-1] + 1)
    if a[i] > a[i-1]:
        g[i] = min(f[i-1]+1,g[i-1]+1)
    if a[i] < a[i-1]:
        f[i] = min(f[i-1]+1,g[i-1]+1)
print(min(f[n-1],g[n-1]))

Solution (Python):

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

res = 1
status = 0
a = A[0]
for i in range(1, N):
    if A[i] > a:
        if status == 1:
            a = A[i]
        elif status == 0:
            a = A[i]
            status = 1
        elif status == -1:
            res += 1
            status = 0
            a = A[i]
    elif A[i] < a:
        if status == 1:
            res += 1
            status = 0
            a = A[i]
        elif status == 0:
            a = A[i]
            status = -1
        elif status == -1:
            a = A[i]
    else:
        pass
    
print(res)

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

def try_inc(i):
    while i < n:
        if i+1 == n or xs[i+1] < xs[i]:
            return i+1
        i += 1
    return i

def try_dec(i):
    while i < n:
        if i+1 == n or xs[i+1] > xs[i]:
            return i+1
        i += 1
    return i

i = 0
ans = 0
while i < n:
    i = max(try_inc(i), try_dec(i))
    ans += 1
print(ans)

Solution (Python):








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

ans = 1
ind = 0
flag = 0
bef = 0

while ind < N:
	now = A[ind]
	if bef == 0:
		bef = now
	elif flag == 0:
		if now == bef:
			()
		elif now < bef:
			bef = now
			flag = -1
		else:
			bef = now
			flag = 1
	elif now != bef:
		if flag == 1:
			if now < bef:
				ans += 1
				flag = 0
		elif flag == -1:
			if now > bef:
				ans += 1
				flag = 0
	bef = now
	ind += 1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
if n <= 2:
    print(1)
    exit()


def mode(a,b):
    if a<b:
        return 1
    elif a == b:
        return 0
    else:
        return -1
cnt = 1
m = mode(a[0], a[1])
for i in range(1, n):
    nm = mode(a[i-1], a[i])
    if nm != m:
        if m == 0:
            m = nm
        elif nm == 0:
            pass
        else:
            m = 0
            cnt += 1
print(cnt)

Solution (Python):
import sys

def rd():
        return sys.stdin.readline().rstrip()

N = int(rd())
A = [ int(x) for x in rd().split() ]

r = 1
d = 0
for i in range(1, len(A)):
        if A[i-1] == A[i]:
                continue
        elif A[i-1] < A[i]:
                if d < 0:
                        r += 1
                        d = 0
                else:
                        d = 1
        else:
                if d > 0:
                        r += 1
                        d = 0
                else:
                        d = -1
print r

Solution (Python):


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

inc = None
prev = None
ans = 0
for i, a in enumerate(As):
    if i == 0:
        ans += 1
    elif inc is None:
        if a > prev:
            inc = True
        elif a < prev:
            inc = False
    else:
        if (inc and a < prev) or (inc == False and a > prev):
            ans += 1
            inc = None
    prev = a
print(ans)

Solution (Python):
N = input()
A = map(int, raw_input().split())
d = 0
ans = 0
for i in xrange(N-1):
    dd = A[i+1] - A[i]
    if dd * d < 0:
        ans += 1
        d = 0
    else:
        if abs(dd) > 0:
            d = dd
print ans + 1