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 = int(input())
A = list(map(int,input().split()))
if N == 1 or len(list(set(A))) == 1:
    print(1)
    exit()
def rec(list1,t):
    for i in range(1,len(list1)):
        if list1[i] - list1[i-1] > 0:
            note = "not decrease"
            break
        elif list1[i] - list1[i-1] < 0:
            note = "not increase"
            break
    for i in range(1,len(list1)):
        if note == "not decrease" and  list1[i] - list1[i-1] < 0:
            return rec(list1[i:],t+1)
        elif note == "not increase" and list1[i] - list1[i-1] > 0:
            return rec(list1[i:],t+1)
    return t
ans = rec(A,1)
print(ans)

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]
def next(v):
    for i in edge[v]:
        if visited[i]:
            continue
        visited[i] = True
        return i
    return -1

from collections import defaultdict
edge = defaultdict(lambda: [])
N, M = inpl()
visited = [False for _ in range(N+1)]
visited[1] = True
for _ in range(M):
    A,B = inpl()
    edge[A].append(B)
    edge[B].append(A)
v = 1
nv = 1
path = [1]
while nv >= 0:
    nv = next(v)
    path.append(nv)
    v = nv
path.pop()
path = list(reversed(path))
v = 1
nv = 1
while nv >= 0:
    nv = next(v)
    path.append(nv)
    v = nv
path.pop()
print(len(path))
print(*path)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
if A[0] <= A[1]:
    di = 1
else:
    di = -1
cnt = 1
i = 1
while i < N:
    if di == 1 and A[i - 1] > A[i]:
        di = -1
        cnt += 1
        i += 1
        if i >= N:
            cnt += 1
    elif di == -1 and A[i - 1] < A[i]:
        di = 1
        cnt += 1
        i += 1
        if i >= N:
            cnt += 1
    i += 1
    
print(cnt)

Submission status: Runtime Error

Solution code:
li = lambda: list(map(int,input().split()))

n,l,t = li()
a,ac,au = [],[],[]
for i in range(n):
    x,y = li()
    if i == 0: start = y
    a.append(x)
    if y == 1:
        ac.append(x)
    else:
        au.append(x)

tt = t%l

if start == 2:
    acc = [n-ac[-s] for s in range(1,len(ac)+1)]
    dist = au[0]+acc[0]
    j = 0
    for i in range(1, min(len(au), len(acc))):
        if dist > tt:
            j = i-1
            break
        if i&1:
            dist += au[i]-au[i-1]
        else:
            dist += acc[i]-acc[i-1]
    if j&1:
        pointofone = n - acc[j//2]
    else:
        pointofone = au[j//2]
else:
    acc = [-au[0]] + [n-ac[-s] for s in range(1, len(ac))]
    dist = acc[0] + au[0]
    j = 0
    for i in range(1, min(len(ac), len(acc)) ):
        if dist > tt:
            j = i-1
            break
        if i&1:
            dist += acc[i]-acc[i-1]
        else:
            dist += au[i]-au[i-1]
    if j == 0:
        pointofone = ac[0]
    elif j&1:
        pointofone = au[j//2]
    else:
        pointofone = n - acc[j//2]

ant = sorted([(s-t)%l for s in au] + [(s+t)%l for s in ac])
st = ant.index(pointofone)
ant = ant[st:]+ant[:st]
print(*ant, sep='\n')

Submission status: Runtime Error

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

ans = 1
inc = a[0] < a[1]

n = len(a)
i = 1
while i < n:
    if (a[i-1] < a[i]) ^ inc:
        ans += 1
        inc = a[i] < a[min(i+1, n-1)]
        i += 2
    else:
        i += 1
print(ans)

Submission status: Runtime Error

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

ans = 1
inc = a[0] < a[1]

n = len(a)
for i in range(1, n):
    if (a[i-1] > a[i]) ^ inc:
        pass
    else:
        ans += 1
        inc = not inc
print(ans)

Submission status: Runtime Error

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

a.sort(reverse=True)

ans = 0
for i in range(n):
    ans += a[2*i+1]

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

ans = 0
i = 1
while i < n-1:
	if arr[i-1] <= arr[i] <= arr[i+1]:
		i += 1
		if i == n-1:
			print ans
			quit()

	elif arr[i-1] >= arr[i] >= arr[i+1]:
		i += 1
		if i == n-1:
			print ans()
			quit()

	else :
		ans += 1
		i += 2

print ans + 1

Submission status: Runtime Error

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

flg = int(a[1]>a[0])
skp = 1
cnt = 1
temp = a[0]
for i in range(1,n):
    dif = a[i] - temp
    direct = int(dif>0)
    if dif != 0:
        if skp:
            flg = direct
            skp = 0
            
        elif direct != flg and skp==0:
            flg = direct
            cnt+=1
            skp = 1
    temp = a[i]
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Submission status: Runtime Error

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

cnt = 1
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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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


print(cnt)

Submission status: Runtime Error

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

if nums[1] >= nums[0]:
    flag = 1
else:
    flag = 2

i = 1
while i < n:
    if flag == 0:
        if nums[i] > nums[i-1]:
            flag = 1
            ans += 1
        else:
            flag = 2
            ans += 1

    elif flag == 1:
        if nums[i] < nums[i-1]:
            flag = 0
            if i == n-1:
                ans += 1
    elif flag == 2:
        if nums[i] > nums[i-1]:
            flag = 0
            if i == n-1:
                ans += 1

    i += 1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
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: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
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([])
        T[k].append(A[i])
    else:
        T[k].append(A[i])
print(k+1)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
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([])
        T[k].append(A[i])
    else:
        T[k].append(A[i])
print(len(T))

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[[A[0],A[1]]]
B=[0]
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([])
        T[k].append(A[i])
    else:
        T[k].append(A[i])
print(len(T))

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
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(A[i-2]>=A[i-1]>=A[i] or A[i-2]<=A[i-1]<=A[i]):
        k+=1
        T.append([])
        T[k].append(A[i])
    else:
        T[k].append(A[i])
print(len(T))

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
x=0
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==1):
  print(1)
  sys.exit()
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: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
x=0
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: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
x=0
for i in range(n-1):
  if(a[i+1-x]==a[i-x]):
    a.pop(i)
    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: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
answer= 1
if n!=1: 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: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
answer,flag = 1,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: Runtime Error

Solution code:
def search(v, A, B, flg, p, c, s):
#  if c > 2:
#    print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  if flg[v-1] == 1:
    return c
  flg[v-1] = 1
  p.append(v)
  c += 1
  for idx in range(len(A)):
    if v == A[idx]:
      cnt = search(B[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  for idx in range(len(B)):
    if v == B[idx]:
      cnt = search(A[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  return c

#
# Main Routine
#
str = input()
NM = list(map(int,str.split()))
#print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])
#  print("A=", A, "B=", B)
#
# Start path finding
#
for i in range(0,int(NM[1])):  # Choose start vertex
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  v = AB[i][0]  # current vertex
  s = v   # start vertex
  p = []
  cnt = search(v, A, B, flg, p, 0, s)
  for idx in range(len(A)):
    if s == A[idx] and B[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  for idx in range(len(B)):
    if s == B[idx] and A[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  if cnt != 0:
    print(cnt)	# If all the conditions are met, output the result and stop.
#    print(p)
    for i in p:
      print(i)
    break

Submission status: Runtime Error

Solution code:
def search(v, A, B, flg, p, c, s):
  if c > 2:
    print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  if flg[v-1] == 1:
    return c
  flg[v-1] = 1
  p.append(v)
  c += 1
  for idx in range(len(A)):
    if v == A[idx]:
      cnt = search(B[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  for idx in range(len(B)):
    if v == B[idx]:
      cnt = search(A[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  return c

#
# Main Routine
#
str = input()
NM = list(map(int,str.split()))
print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])
#  print("A=", A, "B=", B)
#
# Start path finding
#
for i in range(0,int(NM[1])):  # Choose start vertex
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  v = AB[i][0]  # current vertex
  s = v   # start vertex
  p = []
  cnt = search(v, A, B, flg, p, 0, s)
  for idx in range(len(A)):
    if s == A[idx] and B[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  for idx in range(len(B)):
    if s == B[idx] and A[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  if cnt != 0:
    print(cnt)	# If all the conditions are met, output the result and stop.
    print(p)
    for i in p:
      print(i)
    break

Submission status: Runtime Error

Solution code:
def search(v, A, B, flg, p, c, s):
  if flg[v-1] == 1:
    return c
#  print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  flg[v-1] = 1
  for idx in A:
    if v == A[idx]:
      c += 1
      if search(B[idx], A, B, flg, p, c, s) == 0:
        return 0
  for idx in B:
    if v == B[idx]:
      c += 1
      if search(A[idx], A, B, flg, p, c, s) == 0:
        return 0
#  for idx in A:
#    if v==A[idx] and flg[B[idx]-1] == 0:
#      return 0
#  for idx in B:
#    if v==B[idx] and flg[A[idx]-1] == 0:
#      return 0
  p.append(v)
  return c+1

str = input()
NM = list(map(int,str.split()))
print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])
#print(AB)
e = 0  # end vertex
#
# Start path finding
#
for i in range(0,int(NM[1])):  # Choose start vertex
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  c = AB[i][0]  # current vertex
  s = c   # start vertex
  p = []
#  print("A=", A, "B=", B)
  cnt = search(c, A, B, flg, p, 0, s)
  if cnt != 0:
#    print(p)
    print(cnt)
    for i in p:
      print(i)
    break

Submission status: Runtime Error

Solution code:
N = input()
A = []
AD = True
EF = True
ANS = 1

for i in range(0,int(N)):
	A[i] = input()

for i in range(0,int(N)):
	if i >= 1:
		if A[i] > A[i-1] and AD == False and EF == False:
			EF = True
			ANS += 1
		elif A[i] < A[i-1] and AD == True and EF == False:
			EF = True
			ANS += 1
		elif EF == True:
			EF = False
			if A[i] > A[i-1]:
				AD = True
			else:
				AD = False

print(ANS)

Submission status: Runtime Error

Solution code:
N = input()
A = input().split()
AD = True
EF = True
ANS = 0

for i in range(0,int(N)):
	if i >= 1:
		if A[i] >= A[i-1] and AD == False and EF == False:
			EF = True
			ANS += 1
		elif A[i] <= A[i-1] and AD == True and EF == False:
			EF = True
			ANS += 1
		if EF == True:
			if A[i] >= A[i-1]:
				AD = True
				EF = False
			elif A[i] =< A[i-1]:
				AD = False
				EF = False

print(ANS)

Submission status: Runtime Error

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

Submission status: Runtime Error

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, M = map(int, input().split())
    graph = defaultdict(list)

    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].append(B)
        graph[B].append(A)

    route = deque()
    used = set()
    route.appendleft(1)
    used.add(1)
    for n in graph[1]:
        route.append(n)
        used.add(n)
        break

    while True:
        start, end = route[0], route[-1]
        start_ok = True
        for n in graph[start]:
            if n not in used:
                start_ok = False
                route.appendleft(n)
                used.add(n)
                break

        end_ok = True
        for n in graph[end]:
            if n not in used:
                end_ok = False
                route.append(n)
                used.add(n)
                break

        if start_ok and end_ok:
            break

    print(len(route))
    print(*route, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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, M = map(int, input().split())
    graph = defaultdict(list)
    route = []
    for _ in range(M):
        A, B = map(int, input().split())
        if not route:
            route += [A, B]
        graph[A].append(B)
        graph[B].append(A)

    while True:
        start, end = route[0], route[-1]
        start_ok = True
        for n in graph[start]:
            if n not in route:
                start_ok = False
                route = [n] + route
                break

        end_ok = True
        for n in graph[end]:
            if n not in route:
                end_ok = False
                route.append(n)
                break

        if start_ok and end_ok:
            break

    print(len(route))
    print(*route, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

Solution code:
from sys import stdin

def main():
    global lista
    n = int(stdin.readline())
    lista = [int(x) for x in stdin.readline().strip().split()]

    inx = 0
    inx  = cuenta(inx)
    flag = lista[inx] >= lista[inx+1];
    cont = 0
    tempc = 0
    while(inx < len(lista)-1):
        if flag:
            if(lista[inx] >= lista[inx+1]):
                flag = True
                tempc+=1
            else:
                tempc=0
                cont+=1
                flag = inx < len(lista)-2 and lista[inx+1] >= lista[inx+2];
        else:
            if(lista[inx] <= lista[inx+1]):
                flag = False
                tempc+=1
            else:
                tempc=0
                cont+=1
                flag = inx < len(lista)-2 and lista[inx+1] >= lista[inx+2];
        inx+=1
    print(cont+1)

def cuenta(i):
    while(i < len(lista)-1 and lista[i] == lista[i+1]):
        i+=1
    return i

main()

Submission status: Runtime Error

Solution code:
# -*- encoding:uff-8 -*-

inp_N = row_input()
inp_arr = row_input()

N = int(inp_N)
arr = list(map(int, inp_arr.split(" ")))

def no_down(arr):
    for i in range(len(arr)-1):
         if arr[i] > arr[i+1]:
              return False
    return True

def no_up(arr):
    for i in range(len(arr)-1):
         if arr[i] < arr[i+1]:
              return False
    return True
    
result = 1
pop=[]
for i in arr:
    pop.append(i)
    if no_down(pop):
        continue
    elif no_up(pop):
        continue
    else:
        result += 1
        pop=[]
        pop.append(i)
        
print(result)

Submission status: Runtime Error

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:
        z=0
    if z2*z1<0:
        count+=1
    if z2!=0:
        z1=z2

print str(count)

Submission status: Runtime Error

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:
        z=-1
    elif A[i+1]-A[i]==0:
        z=0
    if z2*z1<0:
        count+=1
    if z2!=0:
        z1=z2

print str(count)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
line_list = list()
for _ in range(M):
    a, b = list(map(int, input().split()))
    line_list.append((a, b))

path_points = [ line_list[0][0], line_list[0][1] ]

for i in range(1, M):
    if line_list[i][0] not in path_points and line_list[i][1] not in path_points:
        break

    if   line_list[i][0] in path_points and line_list[i][1] not in path_points:
        path_points.append(line_list[i][1])
    elif line_list[i][1] in path_points and line_list[i][0] not in path_points:
        path_points.insert(0, line_list[i][0])

for point in path_points:
    print(point)

Submission status: Runtime Error

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

X = []
W = []
X_after = []
for _ in range(N):
    x, w = list(map(int, input().split()))
    if w == 1:
        x_after = (x + T) % L
    else:
        x_after = (x - T) % L
        x_after = x_after if x_after >= 0 else L + x_after
    X.append(x)
    W.append(w)
    X_after.append(x_after)

n_colide = 0
for i in range(1, N):
    if W[0] == 1 and W[i] == 2:
        dist = X[i] - X[0]
        n_colide += 2 * (T - (dist / 2)) // L + 1
    elif W[0] == 2 and W[i] == 1:
        dist = (L + X[0]) - X[i]
        n_colide += 2 * (T - (dist / 2)) // L + 1

if W[0] == 1:
    num_after = n_colide % N
else:
    num_after = N - (n_colide % N)

num_after = int(num_after)

x_after_first = X_after[0]
X_after = sorted(X_after)
i = X_after.index(x_after_first)
X_after = X_after[i-num_after:] + X_after[:i-num_after]

for x_after in X_after:
    print(x_after)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = [int(x) for x in sys.stdin.readline().split()]
ans = 1
def checker():
	if l[0]-l[1]>0:
		for i in range(1,n-1):
			if a[i]-a[i+1]>=0:
				continue
			else:
				ans += 1
				for _ in range(i):
					a.pop(0)
	elif l[0]-l[1]<0:
		for i in range(1,n-1):
			if a[i]-a[i+1]<=0:
				continue
			else:
				ans += 1
				for _ in range(i):
					a.pop(0)
	else:
		a.pop(0)

while len(a) != 2:
	checker()

print(ans)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = [int(x) for x in sys.stdin.readline().split()]
ans = 1
def checker():
	if l[0]-l[1]>0:
		for i in range(1,n-1):
			while a[i]-a[i+1]>=0:
				continue
			else:
				ans += 1
				for _ in range(i):
					a.pop(0)
	elif l[0]-l[1]<0:
		for i in range(1,n-1):
			while a[i]-a[i+1]<=0:
				continue
			else:
				ans += 1
				for _ in range(i):
					a.pop(0)
	else:
		a.pop(0)

while len(a) != 2:
	checker()

print(ans)

Submission status: Runtime Error

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

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

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


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

    print count

Submission status: Runtime Error

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

ans = 0
tmp2 = 99
for a1, a2 in zip(A, A[1:]):
    if a1 < a2:
        tmp = 1
    elif a1 > a2:
        tmp = -1
        
    if tmp != tmp2:
        ans = ans + 1
    
    tmp2 = tmp

print ans

Submission status: Runtime Error

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

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=[]
ans2=[0 for i in range(n)]
w1=[]
w2=[]

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

# kはアリ１がずれ違った数。アリ１はアリk+1に進化してる。
if (x[1]+2*t)>l: k=min(w.count(1),w.count(2))
else:
    k=0
    if w[1]==1:
        for i in range(x[1],x[1]+2*t): k+=w2.count(i)
    if w[1]==2:
        for i in range(x[1],x[1]+2*t): k+=w1.count(i)

ans.sort()
for i in range(n):
    ans2[i]=ans[(i+k)%n]
for i in range(n): print(ans2[i])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 1
def incr(a,b):
    if a>b:
        return -1
    elif a==b:
        return 0
    else:
        return 1
init = incr(a[0], a[1])
flag = True
for i in range(1, n-1):
    tmp = incr(a[i], a[i+1])
    #print("a[i]=", a[i]," a[i+1]=", a[i+1], " init=", init, " tmp=", tmp)
    if tmp==0:
        tmp = init
    if init*tmp<0 and flag:
        ans += 1
        init = tmp
        flag = False
        #print(i)
        continue
    init = tmp
    flag = True
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, L, T = map(int, input().split())
X = []
W = []
ant = [i for i in range(N)]
for i in range(N):
    xi, wi = map(int, input().split())
    X.append(xi)
    W.append(wi)

npX = np.array(X).astype(np.float)
npW = np.array(W).astype(np.float)
npW[npW == 2] = -1

def swap(ant, i, j):
    tmp = ant[i]
    ant[i] = ant[j]
    ant[j] = tmp
    return ant

ans = (npX + npW * T) % L

T %= L
if T > L - T:
    T = L - T
    npW *= -1
t = 0
while t < T:
    t += 0.5
    npX = (npX + npW * 0.5) % L
    colision = set([e for e in set(npX) if np.sum(npX == e) == 2])
    if len(colision) != 0:
        for e in colision:
            i, j = np.where(npX == e)[0].tolist()
            swap(ant, i, j)

for i in range(N):
    print(int(ans[ant.index(i)]))

Submission status: Runtime Error

Solution code:
n = int(input())
aString = str(input())

aStringAry = aString.split(' ')
aIntAry = []
for i in range(n-1):
    if aStringAry[i] != aStringAry[i + 1]:
        aIntAry.append(int(aStringAry[i]))
aIntAry.append(int(aStringAry[n - 1]))

answer = 0

kioku = 0
for i in range(len(aIntAry)):
    if i + 2 <= n:
        #print(str(i))
        #print(str(aIntAry[i]))
        #print(str(aIntAry[i + 1]))
        if kioku == 0:
            kioku = aIntAry[i + 1] - aIntAry[i]
            continue
        else:
            if kioku == aIntAry[i + 1] - aIntAry[i]:
                kioku = aIntAry[i + 1] - aIntAry[i]
                continue
            else:
                kioku = 0
                answer += 1
                continue

answer += 1

print(answer)

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