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: Accepted

Solution code:
import numpy as np

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

cnt = 1
direct = 0
temp = a[0]
for i in range(1,n):
    dif = a[i] - temp
    if dif != 0:
        if direct == 0:
            direct = np.sign(dif)
            
        elif np.sign(a[i] - temp) != direct:
            cnt+=1
            direct = 0
    temp = a[i]
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

count = 1
direction = 0
temp = A[0]
for i in range(1, N):
    diff = A[i] - temp
    if diff != 0:
        if direction == 0:
            direction = np.sign(A[i] - temp)
        else:
            if np.sign(A[i] - temp) != direction:
                count += 1
                direction = 0
    temp = A[i]

print(count)

Submission status: Accepted

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

def solve(N, A):
    s = 0
    result = 1
    for i in range(N-1):
        r = A[i+1] - A[i]
        if r * s < 0:
            result += 1
            s = 0
        elif r != 0:
            s = r
    return result

print(solve(N, A))

Submission status: Accepted

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

def solve(N, A):
    if N <= 2:
        return 1
    s = 0
    result = 1
    i = 0
    while i < N-1:
        r = A[i+1] - A[i]
        if (r > 0 and s < 0) or (r < 0 and s > 0):
            result += 1
            s = 0
        elif r != 0:
            s = r
        i += 1
    return result

print(solve(N, A))

Submission status: Accepted

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

flg=0
ans=1

for i in range(N-1):
  if flg==0 and A[i]>A[i+1]:
    flg=-1
  elif flg==0 and A[i]<A[i+1]:
    flg=1
  elif flg==1 and A[i]>A[i+1]:
    flg=0
    ans+=1
  elif flg==-1 and A[i]<A[i+1]:
    flg=0
    ans+=1
  else:
    continue
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n <= 2:
	print(1)
else:
	b = [a[0]]
	for i in range(1, n):
		if a[i-1] != a[i]:
			b.append(a[i])

	ans = 1

	def upper(x):
		if x[0] < x[1]:
			return True
		else:
			return False

	array = [b[0], b[1]]

	i = 2
	while i < len(b):
		u = upper(array)
		if (u and b[i] > array[-1]) or (not u and b[i] < array[-1]):
			array.append(b[i])
			i += 1
		else:
			ans += 1
			if i == len(b) - 1:
				break
			array = [b[i], b[i+1]]
			i += 2

	print(ans)

Submission status: Accepted

Solution code:
import sys

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

cnt = 1
if n ==1:
    print(cnt)
    exit()

tmp = array.pop(0)
tmp2 = array.pop(0)
mode = "plus" if tmp2 > tmp else "minus" if tmp2 != tmp else "equal"
tmp = tmp2

for i in array:
    if tmp < i:
        if mode == "minus":
            cnt += 1
            mode = "equal"
        elif mode == "equal":
            mode = "plus"
    elif tmp > i:
        if mode == "plus":
            cnt += 1
            mode = "equal"
        elif mode == "equal":
            mode = "minus"
    tmp = i
print(cnt)

Submission status: Accepted

Solution code:
def sign(x):
    if x == 0:
        return 0
    return x // abs(x)


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

    if n == 1:
        print(1)

    else:
        cnt = 1
        d = sign(a[1]-a[0])
        for i in range(n-1):
            dd = sign(a[i+1]-a[i])
            if d == 0:
                d = dd

            if d != 0 and dd != 0 and d != dd:
                cnt += 1
                if i < n-2:
                    d = sign(a[i+2]-a[i+1])

        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

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

if N <= 2:
    print(1)
    sys.exit(0)

count = 0
status = 0
for i in range(1,N):
    # print(A[i-1],A[i], status)
    if A[i-1] == A[i]:
        new_status = 0
        continue
    elif A[i-1] < A[i]:
        new_status = 1
    elif A[i-1] > A[i]:
        new_status = -1
    if status == 0:
        status = new_status
        continue
    if status == new_status:
        continue
    else:
        count += 1
        # print("c")
        status = 0

print(count+1)

Submission status: Accepted

Solution code:
def a_sorted_arrays(N, A):
    ans = 0  # 条件を満たすように数列に区切り線を入れるとき、その本数を解とする
    change = 0  # 数列の変化の仕方。1なら増加、0なら横ばい、-1なら減少
    for k in range(1, N):
        if change == 0:
            # 数列が横ばい状態でなくなるまで数列を見る
            if A[k] > A[k - 1]:
                change = 1
            elif A[k] < A[k - 1]:
                change = -1
        elif change == 1:
            if A[k] < A[k - 1]:
                # 数列が非減少状態から変化した。ここで数列を区切る
                change = 0
                ans += 1
        elif change == -1:
            if A[k] > A[k - 1]:
                # 数列が非増加状態から変化した。ここで数列を区切る
                change = 0
                ans += 1
    ans += 1  # 数列の末尾で区切る分、1足す
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(a_sorted_arrays(N, A))

Submission status: Accepted

Solution code:
N=int(input())
A=list((input().split()))
direction=0 #方向、上が1,下が-1
number=int(A[0])#初期値
count=0

for i in range (1, N):
    if direction==0:
        if int(A[i])>number:
            direction=1
        elif  int(A[i])<number:
            direction=-1
        else:
            direction=0
    elif direction==1:
        if int(A[i])<number:
            direction=0
            count+=1
    elif direction==-1:
        if int(A[i])>number:
            direction=0
            count+=1
    number=int(A[i])

count+=1
print(count)

Submission status: Accepted

Solution code:
n=int(input())
du=""
f=True
ans=1
for j in input().split():
  i=int(j)
  if f==True:
    i0=i
    f=False
  if (du=="u" and i<i0) or (du=="d" and i>i0):
    ans+=1
    du=""
  elif i > i0:
    du="u"
  elif i < i0:
    du="d"
  i0=i
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 1
dec = False
start = True
now = A[0]
for nex in A[1:]:
    if nex-now>0:
        if start:
            start=False
            dec=False
        elif dec:
            start=True
            ans += 1
    elif nex-now<0:
        if start:
            start=False
            dec=True
        elif not dec:
            start=True
            ans += 1
    now = nex

print(ans)

Submission status: Accepted

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

i = int(0)
ans = int(0)
f = True


while i+1 < n:

    if a[i] < a[i+1] :
        while a[i] <= a[i+1] :
            if i+1 >= n-1:
                f=False
                break
            i += 1
        
        if f :
            ans += 1

    elif a[i] == a[i+1] :
        if i+1 >= n-1:
            break

    else:
        while a[i] >= a[i+1] :
            if i+1 >= n-1:
                f = False
                break
            i+=1
        
        if f :
            ans += 1
    
    i += 1

    
print(ans+1)

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int,input().split()))
ans = 0
i = 0

while i < n:
    j, k = i, i
    while j < n - 1 and nums[j] <= nums[j+1]:
        j += 1
    while k < n - 1 and nums[k] >= nums[k+1]:
        k += 1
    i = max(j , k) + 1
    ans += 1
print(ans)

Submission status: Accepted

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

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(input())
    a = list(map(int, input().split()))
    assert len(a) == n
    div = 1
    flag = "free"
    for i in range(1, n):
        if flag == "free":
            if a[i] > a[i - 1]:
                flag = "inc"
            elif a[i] < a[i - 1]:
                flag = "dec"
        elif flag == "inc":
            if a[i] < a[i - 1]:
                div += 1
                flag = "free"
        else:
            if a[i] > a[i - 1]:
                div += 1
                flag = "free"
    print(div)

main()

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
if N==1:
    print(1)
    exit()
T=[[A[0],A[1]]]
k=0
for i in range(2,N):
    if len(T[k])<=1:
        T[k].append(A[i])
        continue
    if not((T[k][0]>=A[i-2]>=A[i-1]>=A[i]) or (T[k][0]<=A[i-2]<=A[i-1]<=A[i])):
        k+=1
        T.append([A[i]])
    else:
        T[k].append(A[i])
print(len(T))

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
x=0
if(n==1):
  print(1)
  sys.exit()
for i in range(n-1):
  if(a[i+1-x]==a[i-x]):
    a.pop(i-x)
    n-=1
    x+=1
    if(n==3):break
if(a[0]==a[1]):
  a.pop(0)
  n-=1
if(n==2):
  print(1)
  sys.exit()
til=a[1]-a[0]
x=0
for i in range(n-1):
  tilt=a[i+1]-a[i]
  if(til*tilt<0):
    x+=1
    if(i+2>=n):
      break
    til=a[i+2]-a[i+1]
print(x+1)

Submission status: Accepted

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

ans = 1
status = "Unset"
for i in range(1, N):
    if status == "Unset":
        if A[i-1] < A[i]:
            status = "UP"
        elif A[i-1] > A[i]:
            status = "DOWN"

    else:
        if status == "UP" and A[i-1] > A[i]:
            ans += 1
            status = "Unset"

        if status == "DOWN" and A[i-1] < A[i]:
            ans += 1
            status = "Unset"

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
answer = 1
if n!=1: flag = np.sign(a[1]-a[0])
for i in range(1,n-1):
	num = np.sign(a[i+1]-a[i])
	if flag==0:
		flag = num
	elif num==-flag:
		answer += 1
		flag = 0
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
count = 1
upd = 0
for i in range(N-1):
  s0 = np.sign(A[i+1] - A[i])
  if upd == 0:
    upd = s0
  elif s0 != 0 and s0 != upd:
    upd = 0
    count += 1
print(count)

Submission status: Accepted

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

count = 0
ans = 1
bef = 0
buff = True
for i in A:
    if count == 0:
        count = 1
    elif count == 1:
        if bef < i:
            count += 1
            buff = True
        elif bef > i:
            count += 1
            buff = False
        else:
            pass
    else:
        if buff:
            if bef <= i:
                pass
            else:
                ans += 1
                count = 1
        else:
            if bef >= i:
                pass
            else:
                ans += 1
                count = 1
    bef = i
print(ans)

Submission status: Accepted

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

First = True
ans = 1
status = None
for i in range(1, N):
    if First:
        if A[i-1] < A[i]:
            status = "up"
            First = False
            continue
        elif A[i-1] > A[i]:
            status = "down"
            First = False
            continue

    if (status == "up") & (A[i-1] > A[i]):
        ans += 1
        First = True
        continue

    if (status == "down") & (A[i-1] < A[i]):
        ans += 1
        First = True
        continue

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby


N = int(input())
A = list(map(int, input().split()))
groups = groupby(A)
A_uniq = [g[0] for g in groups]
# print(A_uniq)
N_uniq = len(A_uniq)

ptr = 1
ans = 1
flg = None
while ptr < N_uniq:
    if A_uniq[ptr] > A_uniq[ptr - 1]:
        if flg is None:
            flg = True
        else:
            if flg:
                ptr += 1
                continue
            else:
                ans += 1
                flg = None
    else:
        if flg is None:
            flg = False
        else:
            if flg:
                ans += 1
                flg = None
            else:
                ptr += 1
                continue
    ptr += 1
print(ans)

Submission status: Accepted

Solution code:
def minimumSubSeq(a):
    n = len(a)
    f = [[0 for i in xrange(2)] for j in xrange(n)]
    f[0][0] = 1
    f[0][1] = 1
    for i in xrange(1, n):
        for j in xrange(2):
            f[i][j] = f[i-1][0] + 1
            f[i][j] = min(f[i][j], f[i-1][1] + 1)
            if (j==0 and a[i-1]>=a[i]) or (j==1 and a[i-1]<=a[i]):
                f[i][j] = min(f[i][j], f[i-1][j])
    return min(f[n-1][0], f[n-1][1])

def main():
    n = int(raw_input().strip())
    a = [int(i) for i in raw_input().strip().split()]
    print minimumSubSeq(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
state = 0
max = 0
min = 0
prev = 0
len = 0
ANS = 1
S = input()
A = list(map(int,S.split()))
 
for i in range(0,int(N)):
  len = len + 1
  if state in {0}:	# Initial state
      prev = A[i]
      state = 1
  elif state in {1}: # Newtral state
    if A[i] > prev:
      state = 2
    elif A[i] < prev:
      state = 3
  elif state in {2}: # Acsending state
    if A[i] < prev:
      state = 1
      ANS = ANS + 1
      len = 0
  elif state in {3}: # Descending state
    if A[i] > prev:
      state = 1
      ANS = ANS + 1
      len = 0
  prev = A[i]
#  print('s=', state, 'in=', A[i], 'prev=', prev, 'ANS=', ANS, 'len=', len)
print(ANS)

Submission status: Accepted

Solution code:
N, *A, = map(int, open(0).read().split())
ans = 1; cur = A[0]; mode = 0
for i in range(N):
    if mode == 0:
        if cur < A[i]:
            mode = 1
        elif cur > A[i]:
            mode = 2
    else:
        if (mode == 1 and not cur <= A[i]) or (mode == 2 and not cur >= A[i]):
            ans += 1
            mode = 0
    cur = A[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

com = a[0]
flag = 0
count = 1
for i in range(1, n):
    if flag == 1:
        if com > a[i]:
            flag = 0
            count += 1
    elif flag == -1:
        if com < a[i]:
            flag = 0
            count += 1
    else:
        if com < a[i]:
            flag = 1
        elif com > a[i]:
            flag = -1
    com = a[i]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
src = list(map(int,input().split()))
asc = None
ans = 1
for i in range(N-1):
    d = src[i+1] - src[i]
    if d == 0: continue
    if asc is None:
        asc = d > 0
    elif (asc and d < 0) or (not asc and d > 0):
        ans += 1
        asc = None
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    N = int(input())
    a_list = list(map(int, input().split()))

    ans = 0
    state = None
    for i in range(N - 1):
        if a_list[i] == a_list[i + 1]:
            continue

        now = a_list[i] < a_list[i + 1]
        if state is None:
            state = now
            continue
        if state != now:
            ans += 1
            state = None

    print(ans + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
result = 1
delta = 0
for i in range(1, n):
    if a[i - 1] < a[i]:
        ndelta = +1
    elif a[i - 1] > a[i]:
        ndelta = -1
    else:
        ndelta = 0
    if delta and ndelta and delta != ndelta:
        result += 1
        delta = 0
    elif not delta:
        delta = ndelta
print(result)

Submission status: Accepted

Solution code:
def sorted_arrays():
	n = int(raw_input())
	a = map(int, raw_input().split(" "))
	if n==1:
		print 1
		return
	ans = 1
	tag=0
	for i in range(1, n):
		if a[i-1]<a[i]:
			if tag==0:
				tag=1
			elif tag==-1:
				ans+=1
				# tag=0 because for the next most left subarray
				# we do not know whether increasing or decreasing
				tag=0
		if a[i-1]>a[i]:
			if tag==0:
				tag=-1
			elif tag==1:
				ans+=1
				tag=0
	print ans

if __name__ == "__main__":
	sorted_arrays()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# N = 9
# A = [1, 2, 1, 2, 1, 2, 1, 2, 1]
# N = 7
# A = [1, 2, 3, 2, 1, 999999999, 1000000000]
# N = 6
# A = [1, 2, 3, 2, 2, 1]
# N = 2
# A = [1, 1]
A = A + [A[-1]]

d = 0
i = 0

inc = None
while i < N:
    if inc is None:
        if A[i] < A[i + 1]:
            inc = True
            d += 1
        elif A[i] > A[i + 1]:
            inc = False
            d += 1
        else:
            inc = None
    else:
        if inc:
            if A[i] > A[i + 1]:
                inc = None
        else:
            if A[i] < A[i + 1]:
                inc = None
    i += 1

if inc is None:
    d += 1
print(d)

Submission status: Accepted

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

count = 1
state = 'none'
b = [a[0]]

for i in range(1,n):
    if state=='none':
        before=b.pop()
        now = a[i]
        if before<now:
            b.append(now)
            state='incr'
        elif before>now:
            b.append(now)
            state='decr'
        else:
            b.append(now)
    elif state=='incr':
        before=b.pop()
        now = a[i]
        if before<=now:
            b.append(now)
        else:
            b=[now]
            state='none'
            count+=1
    elif state=='decr':
        before=b.pop()
        now = a[i]
        if before>=now:
            b.append(now)
        else:
            b=[now]
            state='none'
            count+=1
print(count)

Submission status: Accepted

Solution code:
from sys import stdin

def main():
	N = int(stdin.readline().strip())
	array = [int(x) for x in stdin.readline().strip().split()]
	ans,i= 0,0
	while i+1 < N:
		if array[i] < array[i+1]:
			ans+=1
			while i+1 < N and array[i] <= array[i+1]:
				i+=1
			i+=1
		elif array[i] > array[i+1]:
			ans+=1
			while i+1 < N and array[i] >= array[i+1]:
				i+=1
			i+=1
		else:
			i+=1
	if i+1 == N or ans == 0:
		ans+=1
	print(ans)
main()

Submission status: Accepted

Solution code:
import numpy as np

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

ret = 0
i = 0
while i < len(a):
    j = i
    while j < n - 1 and a[j] <= a[j+1]:
        j += 1
    h = i
    while h < n - 1 and a[h] >= a[h+1]:
        h += 1
    i = max(h, j) + 1
    ret += 1

print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
r = range

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

ret = 0
i = 0
while i < len(a):
    j = i
    while j < n - 1 and a[j] <= a[j+1]:
        j += 1
    h = i
    while h < n - 1 and a[h] >= a[h+1]:
        h += 1
#    print(i, j, h)
    i = max(h, j) + 1
    ret += 1

print(ret)

Submission status: Accepted

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

count=1
z1=0
for i in range(N-1):
    if A[i+1]-A[i]>0:
        z2 = 1
    elif A[i+1]-A[i]<0:
        z2 = -1
    elif A[i+1]-A[i]==0:
        z2 = 0
    if z2*z1<0:
        count+=1
        z1=0
    elif z2!=0:
        z1=z2

print str(count)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n = I()
    a = LI()
    t = 0
    c = a[0]
    r = 1
    for b in a[1:]:
        if c == b:
            continue
        if t==0:
            t = c-b
        elif t * (c-b) < 0:
            r += 1
            t = 0

        c = b

    return r


print(main())

Submission status: Accepted

Solution code:
# 整数の入力
n=int(input())
a=list(map(int, input().split()))

p=1
flag=0 #増加中なら1,減少中なら-1

for i in range(1,n):
  if a[i-1]<a[i]:
    if flag>=0:#継続
      flag=1
    if flag==-1:#切断
      flag=0
      p+=1
      i+=1
  if a[i-1]>a[i]:
    if flag<=0:#継続
      flag=-1
    if flag==1:#切断
      flag=-0
      p+=1
      i+=1
print(p)

Submission status: Accepted

Solution code:
import sys

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

    ans = 0

    mode = 0

    for i in range(1, n):
        if a[i] > a[i - 1]:
            if mode == -1:
                ans += 1
                mode = 0
            else:
                mode = 1
        elif a[i] < a[i - 1]:
            if mode == 1:
                ans += 1
                mode = 0
            else:
                mode = -1
        else:
            pass

    ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

count=0
p=0

def cal():
	global p
	global count
	global a,n
	

	
	while True:
		while p + 1 < len(a) and a[p + 1] == a[p]:
			p += 1
		if p + 1 >= len(a):
			return count + 1
		
		if a[p+1]>a[p]:
			while p+1<len(a) and a[p+1]>=a[p]:
				p+=1
			if p+1>=len(a):
				return count+1
		else:
			while p+1<len(a) and a[p+1]<=a[p]:
				p+=1
			if p+1>=len(a):
				return count+1
		count+=1
		p+=1

print cal()

Submission status: Accepted

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
bd = 0
skip = False
UP = 1
DOWN = -1
stat = 0
for i in range(1, n):
	diff = a[i] - a[i - 1]
	if diff == 0:
		continue

	if stat == 0:
		if diff > 0:
			stat = UP
		else :
			stat = DOWN

		continue

	if stat == UP and diff < 0:
		x += 1
		stat = 0
		continue

	if stat == DOWN and diff > 0:
		x += 1
		stat = 0

print(str(x))

Submission status: Accepted

Solution code:
def cutter(nums, idx):
    if len(nums) - idx <= 2:
        return len(nums)
    
    for i in xrange(idx+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 len(nums)

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

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


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

    print count

Submission status: Accepted

Solution code:
# coding: utf-8
# AGC 013 a 
# Here your code !
n = input()
if n <= 2:
    print 1
    exit()
    
a = map(int, raw_input().split())

c = 1

status = "n"
i = 1
while i < n:
    if status == "n":
        if a[i-1] < a[i]:
            status = "i"
        elif a[i-1] > a[i]:
            status = "d"
        i += 1
        
    elif status == "i":
        if a[i-1] <= a[i]:
            i += 1
        elif a[i-1] > a[i]:
            status = "n"
            c += 1
            i += 1
        
    elif status == "d":
        if a[i-1] < a[i]:
            status = "n"
            c += 1
            i += 1
        elif a[i-1] >= a[i]:
            i += 1
print c

Submission status: Accepted

Solution code:
from operator import le, ge

n = int(input())

a_list = list(map(int, input().split()))
prev_a = a_list[0]
cmp = None
cmps = [le, ge]
ans = 1
for a in a_list[1:]:
    if cmp is None:
        if prev_a < a:
            cmp = cmps[0]
        elif prev_a > a:
            cmp = cmps[1]
    else:
        if not cmp(prev_a, a):
            ans += 1
            cmp = None
    prev_a = a

print(ans)

Submission status: Accepted

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
		last = x
	else:
		if (x-last) * state >= 0:
			last = x
		else:
			last = x
			state = 0
			cnt += 1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#AGC013A

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

Submission status: Accepted

Solution code:
#coding=UTF-8
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
#        print('case 1')
    else:
        if subseq_muki==None:
            if subseq_mae==mono:
                subseq_mae=mono
#                print('case 2')
            elif subseq_mae>mono:
                #減少パターン
                subseq_muki=-1
                subseq_mae=mono
#                print('case 3')
            else:
                subseq_muki=1
                subseq_mae=mono
#                print('case 4')
                
        elif (mono - subseq_mae) * subseq_muki >= 0:
            #増加減少の向きが合うとき
            #ここでは横這いのときもok
            subseq_mae=mono
#            print('case 5')
        else:
            #そうで無ければ仕切り直し
            subseq_mae=mono
            subseq_nth+=1
            subseq_muki=None
#            print('case 6')

#後処理
pass

print(subseq_nth)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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
        a = 0
    else:
        pass

print(count+1)

Submission status: Accepted

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
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)