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:
n=int(input())
a = list(map(int,input().split()))
cnt=1
index=0
state=""
while index+1 < n:
    if state=="low" and a[index]<a[index+1]:
        state=""
        cnt+=1
        index+=1
    elif state=="high" and a[index]>a[index+1]:
        state=""
        cnt+=1
        index+=1
    elif a[index]<a[index+1]:
        state="high"
        index+=1
    elif a[index]>a[index+1]:
        state="low"
        index+=1
    else:
        index+=1
print(cnt)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

result = 0
i = 0

while(i < N - 1):
  if(l[i] == l[i + 1]):
    i += 1
    continue
  elif(l[i] < l[i + 1]):
    while(i < N - 1 and l[i] <= l[i + 1]):
      i += 1
  else:
    while(i < N - 1 and l[i] >= l[i + 1]):
      i += 1
  result += 1
  i += 1

if(i == N - 1):
  result += 1
  
print(result)

Submission status: Accepted

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

# i = 0
# def w(i):
#     # print(i)
#     if A[i] - A[i-1] == 0:
#         return 0
#     else:
#         return (A[i]-A[i-1]) / abs(A[i]-A[i-1])
# v = w(1)
# ans = 1

# i = 2
# while i < n:
#     print(i)
#     nv = w(i)
#     if nv * v < 0:
#         ans += 1
#         i += 2
#         v = 0
#         if i == n:
#             print("p")
#             ans += 1
#     else:
#         i += 1
#     if nv != 0:
#         v = nv

B = []
for i in range(1, n):
    if A[i] != A[i-1]:
        B.append(int((A[i]-A[i-1]) / abs(A[i]-A[i-1])))
# print(B)

ans = 1
t = 0
m = 0
for i in range(len(B)):
    # print(i)
    if B[i] * t < 0:
        # print("p")
        ans += 1
        t = 0
        if i == len(B):
            ans += 1
    else:
        t = B[i]

print(ans)

Submission status: Accepted

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

for i in range(1,N):
  d = A[i] - A[i-1]
  if c == 0:
    c = d
  elif c*d < 0:
    C += 1
    c = 0
print(C)

Submission status: Accepted

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

N = int(input().split()[0])
a_list = list(map(int, input().split()))

c = 0
is_minus = True
start_flag = True

for i in range(1, N):
    if start_flag:
        if a_list[i] == a_list[i - 1]:
            continue
        is_minus = True if a_list[i] < a_list[i - 1] else False
        start_flag = False
        continue

    if is_minus:
        if a_list[i] > a_list[i - 1]:
            c += 1
            start_flag = True
    else:
        if a_list[i] < a_list[i - 1]:
            c += 1
            start_flag = True

ans = c + 1
print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = 0
    cnt = 1
    for i in range(1, n):
        if a[i] > a[i-1]:
            if b == 0:
                b = 1
            elif b == -1:
                cnt += 1
                b = 0
        elif a[i] < a[i-1]:
            if b == 0:
                b = -1
            elif b == 1:
                cnt += 1
                b = 0
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
now=0
p=a[0]
cnt=1
for i in range(n):
	if a[i]>p:
		if now=="-":
			cnt+=1
			now=0
		else:
			now="+"
	elif a[i]<p:
		if now=="+":
			cnt+=1
			now=0
		else:
			now="-"
	p=a[i]
print(cnt)

Submission status: Accepted

Solution code:
_ = input()
N = list(map(int, input().split()))
pren = N[0]
preud = 0 # up = 1, down = -1
cnt = 0
for n in N:
  # 初めに方向の評価
  if pren < n:
    ud = 1
  elif pren > n:
    ud = -1
  else:
    ud = 0
  # 逆方向
  if preud * ud == - 1:
    cnt += 1
    preud = 0
  else:
    if ud != 0:
      preud = ud
  pren = n
#  print(ud, preud)
print(cnt+1)

Submission status: Accepted

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

for a in A:
    if B[-1] != a:
        B.append(a)

N = len(B)
ans = 1
prev = -1
for i in range(1, N - 1):
    if B[i - 1] < B[i] and B[i + 1] < B[i]:
        if i - prev > 1:
            ans += 1
            prev = i
    elif B[i - 1] > B[i] and B[i + 1] > B[i]:
        if i - prev > 1:
            ans += 1
            prev = i

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
m=0
c=1
for i in range(1,N):
  d=A[i]-A[i-1]
  if m==0:m=d
  elif m*d<0:
    c+=1
    m=0
print(c)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
mono=0
c=1
for i in range(1,N):
  d=A[i]-A[i-1]
  if mono==0:
    mono=d
  elif mono*d<0:
    c+=1
    mono=0
print(c)

Submission status: Accepted

Solution code:
n = input()
l = list(map(int, input().split()))
s = 0
now = l[0]
count = 0
for i in range(1, len(l)):
    if s == 0:
        if l[i] > now:
            s = 1
        elif l[i] < now:
            s = -1
    elif s == 1:
        if not (l[i] >= now):
            count += 1
            s = 0
    else:
        if l[i] > now:
            count += 1
            s = 0
    now = l[i]
print(count + 1)

Submission status: Accepted

Solution code:
N,*A=map(int,open(0).read().split());f=a=0
for i,j in zip(A,A[1:]):
 if f:
  if(f<0)&(i<j)|(f>0)&(i>j):a+=1;f=0
 else:f=(i<j)-(i>j)
print(a+1)

Submission status: Accepted

Solution code:
N,*A=map(int,open(0).read().split());f=a=0
for i,j in zip(A,A[1:]):
 if f<0:
  if i<j:a+=1;f=0
 elif f<1:f=(i<j)-(i>j)
 else:
  if i>j:a+=1;f=0
print(a+1)

Submission status: Accepted

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

data = []
for i in range(N-1):
  if a[i+1]-a[i] == 0:
    continue
  else:
    data.append(a[i+1]-a[i])
#print(data)

if len(data) <= 1:
  print(1)
else:
  ans = 0
  left = 0
  i = 0
  while left < len(data)-1:
    if data[left]*data[left+1] < 0: # 極値
      ans += 1
      left += 1
      i = left
    left += 1
  else:
    if i == len(data):
      pass
    else:
      ans += 1
    print(ans)

Submission status: Accepted

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

for i in range(1, N):
    if A[i-1] == A[i]:
        pass
    elif Flag == None:
        Flag = (A[i-1] < A[i])
    elif Flag == (A[i-1] < A[i]):
        pass
    else:
        count += 1
        Flag = None

print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

cnt = 1

if len(arr) == 1:
    print(cnt)
    exit()

a = arr[0]
cmode = 0
nmode = 0
sz = 1
for i in range(1, len(arr)):

    if a > arr[i]:
        nmode = 1
    elif a == arr[i]:
        nmode = cmode
    else:
        nmode = 2

    if cmode != 0:
        if nmode != cmode:
            cnt += 1
            cmode = 0
            sz = 1
        else:
            cmode = nmode
            sz += 1
    else:
        cmode = nmode

    a = arr[i]

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    f = 0
    cnt = 0
    for i in range(n):
        if i != 0:
            if f == 0:
                if a[i] > a[i-1]:
                    f = 1
                elif a[i] < a[i-1]:
                    f = -1
                else:
                    f = 0
            else:
                if f == 1 and a[i] >= a[i-1]:
                    continue
                elif f == -1 and a[i] <= a[i-1]:
                    continue
                else:
                    cnt += 1
                    f = 0
    print(cnt + 1)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/agc013/tasks/agc013_a

n = int(input())
l = list(map(int, input().split()))
flag = None
ans = 1
for i in range(1, n):
    if l[i-1] == l[i]:
        pass
    elif flag == None:
        flag = l[i-1] < l[i]
    elif flag == (l[i-1] < l[i]):
        pass
    else:
        ans += 1
        flag = None
print(ans)

Submission status: Accepted

Solution code:
# AGC013A - Sorted Arrays
def main():
    N, *A = map(int, open(0).read().split())
    ans, cur = 0, A[0]
    flg = 0  # unknown (0), increasing (1), decreasing (2)
    for i in A:
        if (flg == 1 and i < cur) or (flg == 2 and i > cur):  # end of trend
            ans += 1
            flg = 0
        elif not flg and cur < i:  # new increasing trend
            flg = 1
        elif not flg and cur > i:  # new decreasing trend
            flg = 2
        cur = i
    print(ans + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
result = 1
d = 0
for i in range(1, N):
  if A[i - 1] == A[i]:
    continue
  if d == 0:
    if A[i - 1] > A[i]:
      d = -1
    else:
      d = 1
  elif d == 1 and A[i - 1] > A[i]:
    d = 0
    result += 1
  elif d == -1 and A[i - 1] < A[i]:
    d = 0
    result += 1
print(result)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
r = 0
mode = "0"
for i in range(1, N):
  if mode == "-" and As[i] > As[i-1]:
    r += 1
    mode = "0"
  elif mode == "+" and As[i] < As[i-1]:
    r += 1
    mode = "0"
  elif As[i] < As[i-1]:
    mode = "-"
  elif As[i] > As[i-1]:
    mode = "+"
r += 1
print(r)

Submission status: Accepted

Solution code:
N = input()
N =int(N)
nums= list(map(int,input().split(" ")))
ans = 1
tend = 0
before = nums[0]
for a in nums[1:]:
    if (before - a) * tend < 0:
        tend = 0
        ans += 1
    else:
        tend = 1 if before - a > 0  else -1 if before - a < 0 else tend

    before = a

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
As = input().split()
for i in range(N):
    As[i] = int(As[i])
As = np.array(As)


def get_sign(x):
    if x>0:
        return +1
    elif x<0:
        return -1
    else:
        return 0

ans = 1
a0 = None
a1 = None
for a in As:
    if a0 is None:
        a0 = a
    elif a1 is None:
        a1 = a
    else:
        if (get_sign(a-a1)==get_sign(a1-a0))|(get_sign(a1-a0)==0):
            a0 = a1
            a1 = a
        elif get_sign(a-a1)==0:
            pass
        else:
            ans += 1
            a0 = a
            a1 = None
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    _ = int(input())
    A = list(map(int, input().split()))
    pre = A[0]
    ans = 1
    state = 0
    for a in A:
        if state == 0:
            if a > pre:
                state = 1
            if a < pre:
                state = -1
        if state == 1:
            if a < pre:
                ans += 1
                state = 0
        elif state == -1:
            if a > pre:
                ans += 1
                state = 0
        pre = a
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=1
count=0

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

arr = list(map(int, input().split(" ")))

ans = 1
case = 0

for i in range(1, n):
  judge = arr[i] - arr[i-1]
  if case == 0:
    if judge > 0:
      case = 1
    elif judge < 0:
      case = -1
  elif case == 1 and judge < 0 or case == -1 and judge > 0:
    case = 0
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# sys.stdin.readline
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = list(map(int, input().split()))

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


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

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

ans = 1
sgn = 0
for i in range(1, N):
    if sgn == 0:
        if A[i] > A[i - 1]:
            sgn = 1
        elif A[i] < A[i - 1]:
            sgn = -1
    elif sgn == 1 and A[i] < A[i - 1] or sgn == -1 and A[i] > A[i - 1]:
        ans += 1
        sgn = 0
print(ans)

Submission status: Accepted

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

count = 1
mode = None
for i in range(n):
    if i+1 == n or arr[i+1] - arr[i] == 0:
        continue
    elif mode is None:
        if arr[i+1] > arr[i]:
            mode = 'up'
        elif arr[i+1] < arr[i]:
            mode = 'down'
    elif mode == 'up':
        if arr[i+1] < arr[i]:
            count += 1
            mode = None
    elif mode == 'down':
        if arr[i+1] > arr[i]:
            count += 1
            mode = None

print(count)

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
a=b=c=0;l+=[0,1]
while a<n:
	while l[a]<=l[a+1]:a+=1
	while l[b]>=l[b+1]:b+=1
	a=b=max(a,b)+1
	c+=1
print(c)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 1
mode = 0

for i in range(1, N):
    if A[i-1] > A[i]:
        if mode == "+":
            cnt += 1
            mode = 0
        else:
            mode = "-"
    elif A[i-1] < A[i]:
        if mode == "-":
            cnt += 1
            mode = 0
        else:
            mode = "+"
            
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    res = 1
    mode = "0"
    for i in range(n - 1):
        if a[i] > a[i + 1]:
            if mode == "+":
                res += 1
                mode = "0"
            else:
                mode = "-"
        elif a[i] < a[i + 1]:
            if mode == "-":
                res += 1
                mode = "0"
            else:
                mode = "+"
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    ix = 0
    cnt = 0
    while(ix < N):
        nix = ix
        minx = 0
        while(nix+1 < N and A[nix] <= A[nix+1]):
            minx += 1
            nix += 1
        nix = ix
        maxx = 0
        while(nix+1 < N and A[nix] >= A[nix+1]):
            maxx += 1
            nix += 1
        ix = ix + max(minx, maxx) + 1
        
        cnt += 1

    print(cnt)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
cnt=1
val='0'
for n in range(1,N):
	if a[n-1]==a[n] or (val=='+' and a[n-1]<a[n]) or (val=='-' and a[n-1]>a[n]):
		pass
	elif val=='0':
		 if a[n-1]<a[n]:
		 	val='+'
		 elif a[n-1]>a[n]:
		 	val='-'
	else:
		val='0'
		cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
cnt=1
val='0'
for n in range(1,N):
	if a[n-1]==a[n] or (val=='+' and a[n-1]<a[n]) or (val=='-' and a[n-1]>a[n]):
		pass
	elif val=='0':
		 if a[n-1]<a[n]:
		 	val='+'
		 elif a[n-1]>a[n]:
		 	val='-'
	else:
		val='0'
		cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()][::-1]
count = 0
f = 0
c = a.pop()
for i in range(1,n):
  c,p = a.pop(),c
  if f == 0:
    if c < p:
      f = 1
    elif c > p:
      f = 2
  if f == 1:
    if c > p:
      count += 1
      f = 0
  if f == 2:
    if c < p:
      count += 1
      f = 0
print(count + 1)

Submission status: Accepted

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

ans = 0
l = 0
ud = 0
for a in A:
  if l==0:
    ans += 1
    l+=1
  elif l==1:
    if b<a:
      ud = 1
      l+=1
    elif b>a:
      ud = -1
      l+=1
  else:
    if b<a and ud == -1:
      ans += 1
      l = 1
    elif b>a and ud == 1:
      ans += 1
      l = 1
  b = a
print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

count = 1
mode = None
for i in range(1, N):
    if A[i-1] == A[i]:
        continue

    if mode == None:
        if A[i-1] < A[i]:
            mode = 'inc'
        if A[i-1] > A[i]:
            mode = 'dec'
        continue

    if mode == 'inc' and A[i-1] < A[i]:
        continue

    if mode == 'dec' and A[i-1] > A[i]:
        continue

    count += 1
    mode = None

print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
flag = "a"
count = 0
for i in range(1,N):
    if A[i-1]<A[i] and flag == "a":
        flag = "up"
    elif A[i-1]>A[i] and flag == "a":
        flag = "down"
    elif A[i-1]==A[i] and flag == "a":
        continue
    if A[i-1]<=A[i] and flag == "up":
        continue
    elif A[i-1]>=A[i] and flag == "down":
        continue
    elif A[i-1]<A[i] and flag == "down":
        count += 1
        flag = "a"
    elif A[i-1]>A[i] and flag == "up":
        count += 1
        flag = "a"

print(count+1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag = None
ans = 0
for i in range(N-1):
    if flag is None:
        if A[i] < A[i+1]:
            flag = True
        elif A[i+1] < A[i]:
            flag = False
        continue
    if flag:
        if A[i+1] < A[i]:
            ans += 1
            flag = None
    elif not flag:
        if A[i] < A[i+1]:
            ans += 1
            flag = None
ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
flag=0
ans=0
old=s[0]
for i in range(n):
    new=s[i]
    if flag==1 and new<old:
        ans+=1
        flag=0
    elif flag==-1 and new>old:
        ans+=1
        flag=0
    else:
        if new>old:
            flag=1
        elif new<old:
            flag=-1
    old=new
print(ans+1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    u = [0]*n
    r = 1
    for l in range(n):
        if l == r:
            r += 1
        while r < n and a[r-1] <= a[r]:
            r += 1
        u[l] = r
    d = [0]*n
    r = 1
    for l in range(n):
        if l == r:
            r += 1
        while r < n and a[r-1] >= a[r]:
            r += 1
        d[l] = r
    i = 0
    for t in range(n):
        i = max(u[i],d[i])
        if i == n:
            print(t+1)
            return
    return
#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N <= 2: return 1

    i = 0
    count = 0
    while i < N:
        ref = A[i]
        count += 1
        i += 1
        while i < N and A[i] == ref:
            i += 1
        if i < N:
            diff = A[i] - ref
            i += 1
            if diff > 0:
                while i < N and A[i-1] <= A[i]:
                    i += 1
            else:
                while i < N and A[i-1] >= A[i]:
                    i += 1
    return count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

if N <= 2:
  print(1)
  exit()

inc, dec = False, False
cnt = 1

for i in range(N-1):
  if A[i+1] > A[i]:
    inc = True
  elif A[i+1] < A[i]:
    dec = True
  
  if inc and dec:
    cnt += 1
    inc, dec = False, False

print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 0
    i = 0
    while i < n:
        # 右隣が同じにならないようにする
        while i+1 < n and a[i] == a[i+1]:
            i+=1
        # i は n-1 で抜けてくるので、下には引っかからない
        # 右隣の数の方が大きかったら
        if i+1 < n and a[i] < a[i+1]:
            # 右の方が小さくなるまで、次に進める
            while i+1 < n and a[i] <= a[i+1]:
                i += 1
        # 左隣の数の方が小さかったら
        elif i+1 < n and a[i] > a[i+1]:
            # 右の数が大きくなるまで、次に進める
            while i+1 < n and a[i] >= a[i+1]:
                i += 1
        # a[i]まで切り取る
        ans += 1
        # i をインクリメントして、新しい配列の先頭とする
        i += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if n <= 2:
  print(1)
  exit()

dec, inc = False, False
cnt = 1

for i in range(n-1):

  if a[i+1] - a[i] < 0:
    dec = True
  elif a[i+1] - a[i] > 0:
    inc = True

  if dec and inc:
    cnt += 1
    dec, inc = False, False

print(cnt)

Submission status: Accepted

Solution code:
'''
左端から条件を満たすようにしていく
Image :
[success] + [Failure]
[success] + [success] + [failure]
'''
N = int(input())
para = [int(i) for i in input().split()]
#logの数で判断
log = [para[0]]
p = 1 
flag_a = False
flag_b = False 
cnt = 1
while p <= N -1:
    if not flag_a and not flag_b :
        if para[p] > log[0]: 
            flag_a = True
            log.append(para[p])
            p += 1
        elif para[p] < log[0] : 
            flag_b = True
            log.append(para[p]) 
            p += 1
        else :
            log.append(para[p])
            p += 1
            continue
        
    else :
        if flag_a:
            if para[p] >= log[-1] :
                log.append(para[p])
                p += 1
            else :
                log = [para[p]]
                flag_a = False
                cnt += 1 
        if flag_b :
            if para[p] <= log[-1] :
                log.append(para[p])
                p += 1
            else :
                log = [para[p]]
                flag_b = False
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(c) for c in input().split(' ')]
#a = [1 ,2 ,1 ,2 ,1 ,2 ,1 ,2 ,1]
l = len(a)
prev = None
c = 1
inc = None

for i in range(l):
    current = a[i]
    if i == 0 :
        continue
    if inc == None:
        if a[i] > a[i-1] :
            inc = True
        elif             a[i] < a[i - 1]:
            inc = False
        else:
            continue 
    elif inc == True:
        if a[i-1] < a[i]:
            pass
        elif a[i -1] > a[i]:
            c += 1
            inc = None
    elif inc == False:
        if a[i-1] > a[i]:
            pass
        elif a[i - 1] < a[i]:
            c += 1
            inc = None
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(n: int, a: "List[int]"):
    i = 0
    res = []
    tmp = [a[0]]
    flag = 0  # -1:単調減少,  0:初期値,  1:単調増加
    while i < len(a)-1:
        if a[i+1] == a[i]:
            tmp.append(a[i+1])
        elif a[i+1] > a[i]:
            if flag != -1:
                tmp.append(a[i+1])
                flag = 1
            else:
                res.append(tmp)
                tmp = []
                tmp.append(a[i+1])
                flag = 0
        elif a[i+1] < a[i]:
            if flag != 1:
                tmp.append(a[i+1])
                flag = -1
            else:
                res.append(tmp)
                tmp = []
                tmp.append(a[i+1])
                flag = 0
        i += 1
    res.append(tmp)
    # print(res)
    print(len(res))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
a=l[0]
l.remove(a)
f='flat'
f2='first'
c=1
for i in l:
  if f2=='first':
    if a==i:
      pass
    elif a<i:
      f='up'
      f2='not first'
      a=i
    else:
      f='down'
      f2='not first'
      a=i
  else:
    if a==i:
      pass
    elif a<i:
      if f=='up':
        pass
        a=i
      else:
        f=='flat'
        f2='first'
        c+=1
        a=i
    else:
      if f=='down':
        pass
        a=i
      else:
        f=='flat'
        f2='first'
        c+=1
        a=i
print(c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    state = 0
    pre = a[0]
    count = 0
    i = 1
    for i in range(1, N):
        tmp = a[i] - pre
        if state == 0: # 状態未定
            if tmp > 0:
                state = 1
            elif tmp < 0:
                state = -1
        elif state == 1: # 単調非減少
            if tmp < 0:
                state = 0
                count += 1
        else:   # 単調非増加
            if tmp > 0:
                state = 0
                count += 1
        pre = a[i]
    count += 1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Flag = None
pre = A[0]
ans = 1
for i in range(1, N):
    a = A[i]
    if a < pre:
        if Flag == "P":
            ans += 1
            Flag = None
        else:
            Flag = "M"
    elif a > pre:
        if Flag == "M":
            ans += 1
            Flag = None
        else:
            Flag = "P"
    pre = a

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 1
now = A[0]
flag = -1
for i in range(1, N):
    d = A[i] - now
    if d == 0:
        continue
    elif d > 0:
        if flag == 0:
            ans += 1
            flag = -1
        else:
            flag = 1
    else:
        if flag == 1:
            ans += 1
            flag = -1
        else:
            flag = 0
    now = A[i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = 0
c = True
cnt = 1
for i in range(len(a)):
    if b == 0:
        b += 1
    else:
        if b == 1:
            if a[i] > a[i-1]:
                c = True
                b += 1
            elif a[i] < a[i-1]:
                c = False
                b += 1
        else:
            if c:
                if a[i] < a[i-1]:
                    cnt += 1
                    b = 1
            else:
                if a[i] > a[i-1]:
                    cnt += 1
                    b = 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 0
    i = 0
    while i < n:
        # 右隣が同じにならないようにする
        while i+1 < n and a[i] == a[i+1]:
            i+=1
        # i は n-1 で抜けてくるので、下には引っかからない
        # 右隣の数の方が大きかったら
        if i+1 < n and a[i] < a[i+1]:
            # 右の方が小さくなるまで、次に進める
            while i+1 < n and a[i] <= a[i+1]:
                i += 1
        # 左隣の数の方が小さかったら
        elif i+1 < n and a[i] > a[i+1]:
            # 右の数が大きくなるまで、次に進める
            while i+1 < n and a[i] >= a[i+1]:
                i += 1
        # a[i]まで切り取る
        ans += 1
        # i をインクリメントして、新しい配列の先頭とする
        i += 1
    print(ans)

if __name__ == '__main__':
    main()