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: Runtime Error

Solution code:
n,l,t=map(int,input().split())
x=[0 for i in range(n+1)]
w=[0 for i in range(n+1)]
ans=[0 for i in range(n+1)]
ans2=[0 for i in range(n)]

for i in range(1,n+1):
    x[i],w[i]=map(int,input().split())
    if w[i]==1: ans[i]=(x[i]+t)%l
    if w[i]==2: ans[i]=(x[i]-t+l)%l

ans.pop(0)
print(ans)
k=min(w.count(1),w.count(2))
for i in range(n): ans2[(i+k)%n]=ans[i]
for i in range(n): print(ans2[i])

Submission status: Runtime Error

Solution code:
N = int(raw_input())
a = map(int, raw_input().split(" "))
cnt = 0
tmp = []
df = 0
for x in a:
    print tmp, 
    print cnt
    if len(tmp) == 0:
        tmp.append(x)
        df = 0
        cnt = cnt + 1
    else:
        if tmp[-1] == x:
            pass
        elif tmp[-1] < x:
            if df >= 0:
                tmp.append(x)
                df = 1
            else:
                tmp = []
                tmp.append(x)
                df = 0
                cnt = cnt + 1
        else:
            if df <= 0:
                tmp.append(x)
                df = -1
            else:
                tmp = []
                tmp.append(x)
                df = 0
                cnt = cnt + 1
print cnt

Submission status: Runtime Error

Solution code:
import numpy as np
N = map(int,raw_input().split())
N=N[0]
A = map(int,raw_input().split())
A = np.array(A)
r=A[1]-A[0]
count = 0

r = A[1:] -A[:-1]
r = np.array([_ for _ in r if not _ == 0])
r = r[1:] * r[:-1]
count = len([1 for _ in r if _ <0])

if not count==0:
    print(count+1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
f = 0
if a[1]-a[0]>0.0:
	sign = 1.0
elif a[1]-a[0]<0.0:
	sign = -1.0
else:
	sign = 0.0
	f = 1	
time = 0.0

while time < int(N - 1):
	time = time + 1.0
	if f == 1:
		f = 0
		if a[int(time)]-a[int(time-1)]>0.0:
			sign = 1.0
		elif a[int(time)]-a[int(time-1)]<0.0:
			sign = -1.0
		else:
			sign = 0.0
			f = 1	
	if (a[int(time)]-a[int(time-1)])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[int(time+1)]-a[int(time)]>0.0:
				sign = 1.0
			elif a[int(time+1)]-a[int(time)]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
f = 0
if a[1]-a[0]>0.0:
	sign = 1.0
elif a[1]-a[0]<0.0:
	sign = -1.0
else:
	sign = 0.0
	f = 1	
time = 0.0

while time < int(N - 1):
	time = time + 1.0
	if f == 1:
		f = 0
		if a[int(time)]-a[int(time-1)]>0.0:
			sign = 1.0
		elif a[int(time)]-a[int(time-1)]<0.0:
			sign = -1.0
	if (a[int(time)]-a[int(time-1)])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[int(time+1)]-a[int(time)]>0.0:
				sign = 1.0
			elif a[int(time+1)]-a[int(time)]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
f = 0
if a[1]-a[0]>0.0:
	sign = 1.0
elif a[1]-a[0]<0.0:
	sign = -1.0
else:
	sign = -1.0
	f = 1	
time = 0.0

while time < int(N - 1):
	time = time + 1.0
	if f == 1:
		f = 0
		if a[int(time)]-a[int(time-1)]>0.0:
			sign = 1.0
		elif a[int(time)]-a[int(time-1)]<0.0:
			sign = -1.0
	if (a[int(time)]-a[int(time-1)])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[int(time+1)]-a[int(time)]>0.0:
				sign = 1.0
			elif a[int(time+1)]-a[int(time)]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0.0
f = 0
while time < int(N - 1):
	time = time + 1
	if f == 1:
		f = 0
		if a[int(time)]-a[int(time-1)]>0.0:
			sign = 1.0
		elif a[int(time)]-a[int(time-1)]<0.0:
			sign = -1.0
	if (a[int(time)]-a[int(time-1)])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[int(time+1)]-a[int(time)]>0.0:
				sign = 1.0
			elif a[int(time+1)]-a[int(time)]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
import sys

def check(aStringAry,start,end):
    aaa = end - start
    e = 0
    startc = start
    for ii in range(aaa):
        if aStringAry[startc + 1 + ii] - aStringAry[startc + ii] != 0:
            e = 1
        else:
            start = startc + 1 + ii
    if e == 0:
        return('t')
    mode = 0
    n = 0
    fc = 'f'
    while fc == 'f':
        if aStringAry[start + 1 + n] - aStringAry[start] == 1:
            mode = 1
            fc = 't'
            #print('1')
        elif aStringAry[start + 1 + n] - aStringAry[start] == -1:
            mode = -1
            fc = 't'
            #print('-1')
        else:
            n += 1

    c = end - start
    for i in range(c):
        #print(i)
        #i += 1
        if aStringAry[i + start + 1] - aStringAry[i + start] == 1 and mode == 1:
            #print('a')
            continue
        elif aStringAry[i + start + 1] - aStringAry[i + start] == -1 and mode == -1:
            #print('b')
            continue
        else:
            return('f')
    return('t')

if __name__ == '__main__':
    n = int(input())
    aString = str(input())

    aStringAry = aString.split(' ')
    for i in range(n):
        aStringAry[i] = int(aStringAry[i])

    #print(aStringAry)
    
    answer = 0
    start = 0
    f = 'f'
    while f == 'f':
        count = 0
        c = 't'
        while c == 't':
            count += 1
            #print('check' + str(start) + ',' + str(start + count))
            c = check(aStringAry,start,start + count)
            #print(c)
            if start + count + 1 == n and c == 't':
                answer += 1
                print(answer)
                sys.exit()
            elif start + count + 1 == n and c == 'f':
                answer += 2
                print(answer)
                sys.exit()
        start = start + count
        answer += 1
        #print('start='+str(start))
    print(answer)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
f = 0
while time < int(N - 1):
	time = time + 1
	if f == 1:
		f = 0
		if a[time]-a[time-1]>0.0:
			sign = 1.0
		elif a[time]-a[time-1]<0.0:
			sign = -1.0
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
f = 0
while time < int(N - 1):
	time = time + 1
	if f == 1:
		if a[time]-a[time-1]>0.0:
			sign = 1.0
		elif a[time]-a[time-1]<0.0:
			sign = -1.0
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				f = 1
			time = time + 1



print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < int(N - 1):
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	else:
		sign = 0.0
	

print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < int(N - 1):
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	

print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < N - 1:
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	

print(int(count+1.0))

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < N - 1:
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	

print(int(count+1.0)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < N - 1:
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	

print(count+1.0)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < N - 1:
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		if time < N - 1:
			if a[time+1]-a[time]>0.0:
				sign = 1.0
			elif a[time+1]-a[time]<0.0:
				sign = -1.0
			else:
				sign = 0.0
			time = time + 1
	if a[time]-a[time-1]>0.0:
		sign = 1.0
	elif a[time]-a[time-1]<0.0:
		sign = -1.0
	

print(int(count+1))

Submission status: Runtime Error

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):
	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: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
time = 0
while time < N - 1:
	time = time + 1
	if (a[time]-a[time-1])*sign<0.0:
		count = count + 1.0
		print(sign)
		if time < N - 1:
			if a[time+1]-a[time]>=0.0:
				sign = 1.0
			else:
				sign = -1.0
			time = time + 1

print(int(count+1))

Submission status: Runtime Error

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


N,M = map(int,input().split())
G = [[] for i in range(N)]
visited = [False for i in range(N)]

for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)


s = 0
t = G[s][0]

path = [s,t]
solved = [False, False]
visited[s] = True
visited[t] = True

while(True):
    if not solved[0]:
        for n in G[s]:
            if visited[n]:
                continue
            visited[n] = True
            s = n
            path = [s] + path
            break
        else:
            if solved[1]:
               break 
            solved[0] = True

    if not solved[1]:
        for n in G[t]:
            if visited[n]:
                continue
            visited[n] = True
            t = n
            path = path + [t]
            break
        else:
            if solved[0]:
                break
            solved[1] = True
print(len(path))
print(' '.join((map(lambda x:str(x+1), path))))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
del_a = [a[i+1]-a[i] for i in range(n-1)]
ans = 1
tmp = 0
before = del_a[0]
length = 1 
for i in range(1,n-1):
    tmp = del_a[i]
    if(before*tmp<0)and(length>1):
        length = 1
        ans += 1
    elif(before*tmp<0)and(i==n-2):
        ans+=1
    else:
        length += 1
    before = del_a[i]
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
n=int(input())
data=list(map(int,input().split()))
ans=1
def check(index,v=0):
    global data
    global ans
    if index+1<len(data):
        if data[index]==data[index+1]:
            check(index+1,v)
        elif data[index]<data[index+1]:
            if v==1 or v==0:
                check(index+1,1)
            else:
                ans+=1
                check(index+1,0)
        else:
            if v==-1 or v==0:
                check(index+1,-1)
            else:
                ans+=1
                check(index+1,0)
check(0)
print(ans)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>=0.0:
	sign = 1.0
else:
	sign = -1.0
pre_a = 0.0
for n in a:
	if (n-pre_a)*sign<0:
		count = count + 1
		sign *= -1
	pre_a = n
print(count+1)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0.0
if a[1]-a[0]>0:
	sign = 1.0
else:
	sign = -1.0
pre_a = 0.0
for n in a:
	if (n-pre_a)*sign<0:
		count = count + 1
		sign *= -1
	pre_a = n
print(count+1)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0
if a[1]-a[0]>0:
	sign = 1.0
else:
	sign = -1.0
pre_a = 0.0
for n in a:
	if (n-pre_a)*sign<0:
		count = count + 1
		sign *= -1
	pre_a = n
print(count+1)

Submission status: Runtime Error

Solution code:
N = float(input())
a = list(map(float, input().split()))
count = 0
if a[1]-a[0]>0:
	sign = 1.0
else:
	sign = -1.0
pre_a = 0.0
for n in a:
	if (n-pre_a)*sign<0:
		count = count + 1
	pre_a = n
print(count+1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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: Runtime Error

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

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[:]

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: Runtime Error

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

if n > 1:
    dif = a[1] - a[0]

if dif > 0:
    state = 1
elif dif < 0:
    state = -1
else:
    state = 0

s = 0

if n > 1:
    for i in range(1,n):
        dif = a[i] - a[i-1]

        if state == 1:
            if dif < 0:
                s += 1
                state = 0
        elif state == -1:
            if dif > 0:
                s += 1
                state = 0
        else:
            if dif > 0:
                state = 1
            elif dif < 0:
                state = -1
            else:
                state = 0

print(s+1)

Submission status: Runtime Error

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

dif = a[1] - a[0]

if dif > 0:
    state = 1
elif dif < 0:
    state = -1
else:
    state = 0

s = 0

for i in range(1,n):
    dif = a[i] - a[i-1]

    if state == 1:
        if dif < 0:
            s += 1
            state = 0
    elif state == -1:
        if dif > 0:
            s += 1
            state = 0
    else:
        if dif > 0:
            state = 1
        elif dif < 0:
            state = -1
        else:
            state = 0

print(s+1)

Submission status: Runtime Error

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

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

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)