On a weekend, Qingshan suggests that she and her friend Daniel go hiking. Unfortunately, they are busy high school students, so they can only go hiking on scratch paper.

A permutation $p$ is written from left to right on the paper. First Qingshan chooses an integer index $x$ ($1\le x\le n$) and tells it to Daniel. After that, Daniel chooses another integer index $y$ ($1\le y\le n$, $y \ne x$).

The game progresses turn by turn and as usual, Qingshan moves first. The rules follow:

If it is Qingshan's turn, Qingshan must change $x$ to such an index $x'$ that $1\le x'\le n$, $|x'-x|=1$, $x'\ne y$, and $p_{x'}<p_x$ at the same time.

If it is Daniel's turn, Daniel must change $y$ to such an index $y'$ that $1\le y'\le n$, $|y'-y|=1$, $y'\ne x$, and $p_{y'}>p_y$ at the same time.

The person who can't make her or his move loses, and the other wins. You, as Qingshan's fan, are asked to calculate the number of possible $x$ to make Qingshan win in the case both players play optimally.


-----Input-----

The first line contains a single integer $n$ ($2\le n\le 10^5$) — the length of the permutation.

The second line contains $n$ distinct integers $p_1,p_2,\dots,p_n$ ($1\le p_i\le n$) — the permutation.


-----Output-----

Print the number of possible values of $x$ that Qingshan can choose to make her win.


-----Examples-----

Input
5
1 2 5 4 3
Output
1
Input
7
1 2 4 6 5 3 7
Output
0


-----Note-----

In the first test case, Qingshan can only choose $x=3$ to win, so the answer is $1$.

In the second test case, if Qingshan will choose $x=4$, Daniel can choose $y=1$. In the first turn (Qingshan's) Qingshan chooses $x'=3$ and changes $x$ to $3$. In the second turn (Daniel's) Daniel chooses $y'=2$ and changes $y$ to $2$. Qingshan can't choose $x'=2$ because $y=2$ at this time. Then Qingshan loses.

Difficulty: HARD
Tags: Game theory

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
nums = list(map(int, input().split()))
left = [0] * n
right = [0] * n
for i in range(1, n):
	if nums[i] > nums[i - 1]:
		left[i] = left[i - 1] + 1
for i in range(n - 2, -1, -1):
	if nums[i] > nums[i + 1]:
		right[i] = right[i + 1] + 1

def main():
	ml = max(left)
	mr = max(right)
	if ml != mr:
		return print(0)
	(mlc, mrc) = (left.count(ml), right.count(mr))
	if mlc + mrc == 2:
		for p in range(n):
			if right[p] == mr and left[p] == ml and (not ml % 2):
				return print(1)
	return print(0)
main()


n = int(input())
p = list(map(int, input().split()))
slope = 1
maxi = 0
count = 0
end = {}
for i in range(1, n):
	if p[i] > p[i - 1]:
		slope += 1
	else:
		if slope > maxi:
			maxi = slope
			count = 1
			end = {i - 1: 1}
		elif slope == maxi:
			count += 1
		slope = 1
if slope > maxi:
	maxi = slope
	count = 1
	end = {i - 1: 1}
elif slope == maxi:
	count += 1
slope = 1
f = 0
for i in range(n - 2, -1, -1):
	if p[i] > p[i + 1]:
		slope += 1
	else:
		if slope > maxi:
			maxi = slope
			count = 1
		elif slope == maxi:
			count += 1
			if i + 1 in end:
				f = 1
		slope = 1
if slope > maxi:
	maxi = slope
	count = 1
elif slope == maxi:
	count += 1
	if i + 1 in end:
		f = 1
if count == 2:
	if f == 1:
		if maxi % 2 == 1:
			print(1)
		else:
			print(0)
	else:
		print(0)
else:
	print(0)


import os, io, math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
cuml = [0] * n
cumr = [0] * n
curr = 0
maxi = 0
for i in range(1, n):
	if a[i] > a[i - 1]:
		curr += 1
	else:
		curr = 0
	cuml[i] = curr
	maxi = max(maxi, curr)
curr = 0
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		curr += 1
	else:
		curr = 0
	cumr[i] = curr
	maxi = max(maxi, curr)
l = set()
for i in range(n):
	if cuml[i] == maxi or cumr[i] == maxi:
		l.add(i)
if len(l) >= 2:
	print(0)
	exit()
if maxi % 2 == 0:
	for i in l:
		if cuml[i] == cumr[i]:
			print(1)
		else:
			print(0)
else:
	print(0)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd, sqrt
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
N = int(input())
p = li()
left_down = [0 for i in range(N)]
right_down = [0 for i in range(N)]
left_up = [0 for i in range(N)]
right_up = [0 for i in range(N)]
for i in range(1, N):
	if p[i - 1] < p[i]:
		left_down[i] = 1 + left_down[i - 1]
		left_up[i] = 0
	else:
		left_down[i] = 0
		left_up[i] = 1 + left_up[i - 1]
for i in range(N - 2, -1, -1):
	if p[i] > p[i + 1]:
		right_down[i] = 1 + right_down[i + 1]
		right_up[i] = 0
	else:
		right_down[i] = 0
		right_up[i] = 1 + right_up[i + 1]
up_max_left = [max(left_up[i], right_up[i]) for i in range(N)]
up_max_right = [max(left_up[i], right_up[i]) for i in range(N)]
for i in range(1, N):
	up_max_left[i] = max(up_max_left[i], up_max_left[i - 1])
for i in range(N - 2, -1, -1):
	up_max_right[i] = max(up_max_right[i], up_max_right[i + 1])
res = 0
for i in range(N):
	if left_down[i] <= 1 or right_down[i] <= 1:
		res += 0
	else:
		(M, m) = (left_down[i], right_down[i])
		if m > M:
			(M, m) = (m, M)
		if M == m and M % 2 == 0:
			L = i - left_down[i]
			R = i + right_down[i]
			g = 0
			if L != 0:
				g = max(g, up_max_left[L - 1])
			if R != N - 1:
				g = max(g, up_max_right[R + 1])
			g = max(g, left_up[L], right_up[R])
			if g < M:
				res += 1
print(res)


n = int(input())
p = [0] + list(map(int, input().split())) + [0]
left = [0 for _ in range(n + 3)]
right = [0 for _ in range(n + 3)]
for i in range(2, n + 1):
	if p[i - 1] < p[i]:
		left[i] = left[i - 1] + 1
for i in range(n - 1, 0, -1):
	if p[i + 1] < p[i]:
		right[i] = right[i + 1] + 1
left_less = [0 for _ in range(n + 3)]
right_less = [0 for _ in range(n + 3)]
for i in range(1, n + 1):
	left_less[i] = max(left_less[i - 1], left[i], right[i])
for i in range(n, 0, -1):
	right_less[i] = max(right_less[i + 1], right[i], left[i])
ans = 0
for i in range(1, n + 1):
	mx = max(left[i], right[i])
	if max(left_less[i - left[i] - 1], right_less[i + right[i] + 1]) < mx:
		if p[i] > p[i - 1] and p[i] > p[i + 1]:
			if left[i] == right[i] and left[i] & 1 == 0:
				ans += 1
print(ans)


import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def solve_(arr):
	if len(arr) <= 4:
		return 0
	xrr = [0]
	rise_count = 0
	for (a, b) in zip(arr, arr[1:]):
		if b > a:
			rise_count += 1
		else:
			rise_count = 0
		xrr.append(rise_count)
	yrr = [0]
	rise_count = 0
	for (a, b) in zip(arr[::-1], arr[::-1][1:]):
		if b > a:
			rise_count += 1
		else:
			rise_count = 0
		yrr.append(rise_count)
	yrr = yrr[::-1]
	zrr = [max(a, b) for (a, b) in zip(xrr, yrr)]
	mxrr = max(xrr)
	myrr = max(yrr)
	mzrr = max(zrr)
	if mxrr != myrr:
		return 0
	if mxrr != mzrr:
		return 0
	if zrr.count(mzrr) > 1:
		return 0
	if mzrr % 2:
		return 0
	return 1
for case_num in [0]:
	k = int(input())
	lst = list(map(int, input().split()))
	res = solve(lst)
	print(res)


n = int(input())
ls = [int(x) for x in input().split()]
lss = []
if ls[1] > ls[0]:
	up = 1
else:
	up = 0
tmp = up
cnt = 1
for i in range(1, len(ls)):
	if tmp:
		if ls[i] > ls[i - 1]:
			cnt += 1
		else:
			lss.append(cnt)
			cnt = 2
			tmp = 0
	elif ls[i] < ls[i - 1]:
		cnt += 1
	else:
		lss.append(cnt)
		cnt = 2
		tmp = 1
lss.append(cnt)
m = max(lss)
cnt = lss.count(m)
ans = 0
if cnt == 2:
	for i in range(len(lss) - 1):
		if lss[i] == m and lss[i + 1] == m and (i % 2 != up):
			ans = 1
if m % 2:
	print(ans)
else:
	print(0)


from sys import stdin
n = int(stdin.readline())
lst = tuple(map(int, stdin.readline().split()))
if lst[0] < lst[1]:
	asc = 1
	dsc = 0
else:
	dsc = -1
	asc = 0
arr = [0]
for i in range(2, n):
	if lst[i] > lst[i - 1]:
		if dsc < 0:
			arr.append(dsc - 1)
			dsc = 0
			asc = 1
		else:
			asc += 1
	elif asc > 0:
		arr.append(asc + 1)
		dsc = -1
		asc = 0
	else:
		dsc -= 1
if asc:
	arr.append(asc + 1)
else:
	arr.append(dsc - 1)
arr.append(0)
if len(arr) == 3:
	print(0)
else:
	grad = []
	for i in range(1, len(arr) - 2):
		if arr[i] > 0:
			if arr[i + 1] != -arr[i]:
				continue
			if arr[i] % 2 == arr[i + 1] % 2 == 0:
				continue
			grad.append((arr[i], i))
	max_grad = abs(max(arr, key=abs))
	grad = list(filter(lambda x: x[0] == max_grad, grad))
	if len(grad) == 0:
		print(0)
	else:
		max_idx = []
		for i in range(len(arr)):
			if abs(arr[i]) == max_grad:
				max_idx.append(i)
		if len(max_idx) > 2:
			print(0)
		elif max_idx[0] == grad[0][1]:
			print(1)
		else:
			print(0)


import sys
import math
from math import factorial, inf, gcd
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
sys.setrecursionlimit(10 ** 5)
t = 1
for ii in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	v = []
	v2 = []
	i = 0
	while i + 1 < n:
		j = i
		while i + 1 < n and a[i + 1] > a[i]:
			i += 1
		t1 = i - j + 1
		j = i
		while i + 1 < n and a[i + 1] < a[i]:
			i += 1
		t2 = i - j + 1
		v.append(t1)
		v.append(t2)
		if t1 % 2 == 1 and t1 == t2:
			v2.append(t1)
	p = max(v)
	print(1 if v2.count(p) == 1 and v.count(p) == 2 else 0)


import sys
input = sys.stdin.buffer.readline
N = int(input())
P = list(map(int, input().split()))
DP = [[0] * N for i in range(2)]
for i in range(N - 1):
	if P[i] < P[i + 1]:
		DP[0][i + 1] = DP[0][i] + 1
for i in range(N - 2, -1, -1):
	if P[i] > P[i + 1]:
		DP[1][i] = DP[1][i + 1] + 1
M = max(max(DP[0]), max(DP[1]))
C = 0
for i in range(2):
	for j in range(N):
		if M == DP[i][j]:
			C += 1
ANS = 0
for i in range(N):
	if DP[0][i] == DP[1][i] and DP[0][i] > 0 and (DP[0][i] & 1 == 0):
		if DP[0][i] == M and C <= 2:
			ANS += 1
print(ANS)


import sys

def get_diagram(nums):
	diagram = [0]
	max_ = 0
	abs_maxs = []
	for (i, num) in enumerate(nums):
		if i == 0:
			continue
		if num > nums[i - 1]:
			if diagram[-1] < 0:
				counter = 1
				diagram.append(counter)
			else:
				diagram[-1] = diagram[-1] + 1
		elif num < nums[i - 1]:
			if diagram[-1] > 0:
				counter = -1
				diagram.append(counter)
			else:
				diagram[-1] = diagram[-1] - 1
		else:
			diagram.append(0)
		if abs(diagram[-1]) > max_:
			max_ = abs(diagram[-1])
			abs_maxs = [len(diagram) - 1]
		elif abs(diagram[-1]) == max_:
			abs_maxs.append(len(diagram) - 1)
	return (diagram, abs_maxs)

def solve(nums):
	if len(nums) == 2:
		return 0
	(diagram, abs_maxs) = get_diagram(nums)
	counter = 0
	for i in range(len(diagram) - 1):
		if diagram[i] > 0 > diagram[i + 1]:
			if diagram[i] != abs(diagram[i + 1]):
				continue
			local_best = [i, i + 1]
			if abs(diagram[local_best[0]]) < abs(diagram[abs_maxs[0]]):
				continue
			if abs(diagram[local_best[0]]) == abs(diagram[abs_maxs[0]]) and abs_maxs != local_best:
				continue
			if len(local_best) == 2:
				if abs(diagram[local_best[0]]) % 2 == 0:
					counter += 1
		else:
			continue
	return counter
n = int(sys.stdin.readline().strip())
line = sys.stdin.readline().strip()
values = list(map(int, line.split()))
print(solve(values))


def resi(a, n):
	boj = 0
	b = [1] * n
	c = [1] * n
	i = 0
	maxr = 1
	maxo = 1
	while i + 1 < n:
		if a[i] < a[i + 1]:
			b[i + 1] = b[i] + 1
			if b[i + 1] > maxr:
				maxr = b[i + 1]
		i += 1
	t = n - 1
	while t > 0:
		if a[t - 1] > a[t]:
			c[t - 1] = c[t] + 1
			if c[t - 1] > maxo:
				maxo = c[t - 1]
		t -= 1
	if maxr > maxo:
		ind = b.index(maxr)
		njp = c[ind]
		del b[ind]
		del c[ind]
		if maxr not in b and maxr not in c and (maxr == njp) and (maxr % 2 == 1):
			boj = 1
	else:
		ind = c.index(maxo)
		del c[ind]
		njp = b[ind]
		del b[ind]
		if maxo not in b and maxo not in c and (maxo == njp) and (maxo % 2 == 1):
			boj = 1
	print(boj)
n = int(input())
a = [int(i) for i in input().split(' ')]
resi(a, n)


import sys, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
n = int(inp())
P = [*map(int, inp().split())]
up = P[1] > P[0]
R = []
x = 1
for i in range(1, n):
	nup = P[i] > P[i - 1]
	if up == nup:
		x += 1
	else:
		R += [x if up else -x]
		x = 2
	up = nup
R += [x if up else -x]
m = max((abs(r) for r in R))
L = []
for r in R:
	if abs(r) == m:
		L += [r // m]
if L == [1, -1] and m % 2:
	print(1)
else:
	print(0)


import array
import collections
from collections import defaultdict
import math
mxN = 200000.0 + 10
n = int(input())
a = list(map(int, input().split()))
Rs = [0] * (n + 10)
Ls = [0] * (n + 10)
for i in range(1, n):
	if a[i] > a[i - 1]:
		Ls[i] = Ls[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i + 1] < a[i]:
		Rs[i] = Rs[i + 1] + 1
mx = max(*Rs, *Ls)
c = 0
for i in range(0, n):
	if mx == Rs[i]:
		c += 1
	if mx == Ls[i]:
		c += 1
for i in range(0, n):
	if c == 2 and mx % 2 == 0 and (Ls[i] == Rs[i]) and (Ls[i] == mx):
		print(1)
		exit(0)
print(0)


def process(n, a):
	l = [0] * n
	r = [0] * n
	for i in range(1, n):
		if a[i - 1] < a[i]:
			l[i] = l[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if a[i + 1] < a[i]:
			r[i] = r[i + 1] + 1
	max_path = 0
	for i in range(n):
		max_path = max(max_path, l[i])
		max_path = max(max_path, r[i])
	n_count = 0
	for i in range(n):
		if l[i] == max_path:
			n_count += 1
		if r[i] == max_path:
			n_count += 1
	if n_count > 2:
		return 0
	result = 0
	for i in range(n):
		if not (l[i] > 0 and r[i] > 0):
			continue
		if l[i] != r[i] and (l[i] == max_path or r[i] == max_path) and (n_count == 2):
			return 0
		if max(l[i], r[i]) < max_path:
			continue
		max_odd_l = l[i]
		if l[i] % 2 == 0:
			max_odd_l = l[i] - 1
		max_odd_r = r[i]
		if r[i] % 2 == 0:
			max_odd_r = r[i] - 1
		if max_odd_l < r[i] and max_odd_r < l[i]:
			return 1
	return 0
n = int(input())
a = [int(x) for x in input().split()]
print(process(n, a))


n = int(input())
p = list(map(int, input().split()))
a = [0] * n
b = [0] * n
for i in range(n - 1):
	if p[i] < p[i + 1]:
		a[i + 1] = a[i] + 1
for i in range(n - 1, 0, -1):
	if p[i - 1] > p[i]:
		b[i - 1] = b[i] + 1
x = max(max(a), max(b))
k = sum((x == i or x == j for (i, j) in zip(a, b)))
s = sum((x == i and x == j for (i, j) in zip(a, b)))
if k > 1 or s == 0 or x % 2:
	print(0)
else:
	print(1)


n = int(input())
array = list(map(int, input().split()))
leftToRight = [0 for i in range(n)]
rightToLeft = [0 for i in range(n)]
for i in range(1, n):
	if array[i - 1] < array[i]:
		leftToRight[i] = leftToRight[i - 1] + 1
for i in range(n - 2, -1, -1):
	if array[i + 1] < array[i]:
		rightToLeft[i] = rightToLeft[i + 1] + 1
maxVal = max(max(leftToRight), max(rightToLeft))
maxCount = 0
maxOnSameIdx = 0
for i in range(n):
	if leftToRight[i] == maxVal:
		maxCount += 1
	if rightToLeft[i] == maxVal:
		maxCount += 1
	if leftToRight[i] == maxVal and rightToLeft[i] == maxVal:
		maxOnSameIdx += 1
if maxCount == 2 and maxOnSameIdx == 1 and (maxVal % 2 == 0):
	print(1)
else:
	print(0)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	peak = []
	if arr[0] > arr[1]:
		peak.append([0, 0, 0])
	for i in range(1, n - 1):
		if arr[i - 1] < arr[i] > arr[i + 1]:
			peak.append([i, 0, 0])
	if arr[-1] > arr[-2]:
		peak.append([n - 1, 0, 0])
	m = len(peak)
	if m == 1 and peak[0][0] == 0 or peak[0][0] == n - 1:
		return 0
	for i in range(m):
		idx = peak[i][0]
		(left, right) = (idx - 1, idx + 1)
		p1 = p2 = arr[idx]
		while left >= 0 and arr[left] < p1 or (right < n and arr[right] < p2):
			if left >= 0 and arr[left] < p1:
				p1 = arr[left]
				peak[i][1] += 1
				left -= 1
			if right < n and arr[right] < p2:
				p2 = arr[right]
				peak[i][2] += 1
				right += 1
	v = -float('inf')
	cnt = 0
	same = False
	for (i, left, right) in peak:
		if max(left, right) > v:
			cnt = 1
			v = max(left, right)
			same = left == right
		elif max(left, right) == v:
			cnt += 1
	if cnt > 1:
		return 0
	else:
		return 1 if same and v % 2 == 0 else 0
print(solve())


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7

def toll(aa):
	res = [0] * len(aa)
	for i in range(1, n):
		if aa[i - 1] < aa[i]:
			res[i] = res[i - 1] + 1
	return res

def ok(i):
	(l, r) = (ll[i], rr[i])
	if l > r:
		(l, r) = (r, l)
	if l == 1:
		return False
	if l == r and l & 1 == 0:
		return True
	return False
n = II()
pp = LI()
ll = toll(pp)
rr = toll(pp[::-1])[::-1]
mx = max(ll + rr)
mxi = -1
for i in range(n):
	if ll[i] == mx or rr[i] == mx:
		if mxi == -1:
			mxi = i
		else:
			print(0)
			exit()
print(1 if ok(mxi) else 0)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	peak = []
	for i in range(1, n - 1):
		if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
			peak.append(i)
	if not peak:
		return 0
	bound = {}
	for idx in peak:
		l = idx - 1
		r = idx + 1
		prev = arr[idx]
		cnt = cnt2 = 0
		while l >= 0 and arr[l] < prev:
			cnt += 1
			prev = arr[l]
			l -= 1
		prev = arr[idx]
		while r < n and arr[r] < prev:
			cnt2 += 1
			prev = arr[r]
			r += 1
		bound[idx] = (cnt, cnt2)
		if idx == peak[-1] and r < n:
			bound[n - 1] = (n - r, 0)
		elif idx == peak[0] and l >= 0:
			bound[0] = (0, l + 1)
	val = -float('inf')
	cnt = 0
	key = -1
	for idx in bound:
		if max(bound[idx]) > val:
			val = max(bound[idx])
			cnt = 1
			key = idx
		elif max(bound[idx]) == val:
			cnt += 1
	if cnt > 1:
		return 0
	elif bound[key][0] != bound[key][1]:
		return 0
	else:
		return 0 if max(bound[key]) % 2 else 1
print(solve())


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, A):

	def sign(x):
		if x > 0:
			return 1
		return -1
	deltas = []
	for (x, y) in zip(A, A[1:]):
		if x > y:
			delta = -1
		else:
			assert x < y
			delta = 1
		if deltas and sign(deltas[-1]) == delta:
			deltas[-1] += delta
		else:
			deltas.append(delta)
	deltas = [0] + deltas + [0]
	longest = max((abs(x) for x in deltas))
	slopes = sum((abs(x) == longest for x in deltas))
	if slopes >= 3:
		return 0
	if slopes == 1:
		return 0
	assert slopes == 2
	for (x, y) in zip(deltas, deltas[1:]):
		if abs(x) == longest and abs(y) == longest:
			if x >= 0 and y <= 0:
				if longest % 2 == 0:
					return 1
				return 0
			if x <= 0 and y >= 0:
				return 0
	return 0
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(10000):
		N = random.randint(2, 3)
		A = list(range(1, N + 1))
		random.shuffle(A)
		ans = solve(N, A)
		ans1 = solve1(N, A)
		if ans1 != ans:
			print('tc' + str(_), N, A)
			print(ans, ans1)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, A)
	print(ans)


def solve(P, n):
	trailLengths = [(-1, -1)] * n
	lastIndex = 0
	for i in range(1, n):
		if i == n - 1 or (P[i] > P[i - 1] and P[i] > P[i + 1]) or (P[i] < P[i - 1] and P[i] < P[i + 1]):
			trailLengths[lastIndex] = (trailLengths[lastIndex][0], i - lastIndex)
			trailLengths[i] = (i - lastIndex, trailLengths[i][1])
			lastIndex = i
	maxTrailLength = 0
	freq = {}
	for i in range(n):
		freq[trailLengths[i][0]] = freq.get(trailLengths[i][0], 0) + 1
		maxTrailLength = max(trailLengths[i][0], maxTrailLength)
	maxTrailLengthFreq = freq[maxTrailLength]
	if maxTrailLengthFreq > 2:
		return 0
	totalWinPositions = 0
	for i in range(1, n - 1):
		if not (P[i - 1] < P[i] and P[i + 1] < P[i]):
			continue
		if trailLengths[i][0] != trailLengths[i][1] or trailLengths[i][0] % 2 == 1:
			continue
		if trailLengths[i][0] == maxTrailLength:
			totalWinPositions += 1
	return totalWinPositions
n = int(input())
P = list(map(int, input().split()))
result = solve(P, n)
print(result)


import sys
n = int(sys.stdin.readline().rstrip())
perms = list(map(int, sys.stdin.readline().rstrip().split()))
max_increase = 0
max_decrease = 0
ls = []
is_lost = False
i = 0
while i < n - 1:
	walk = i + 1
	if perms[walk] > perms[i]:
		while walk < n:
			if perms[walk] < perms[walk - 1]:
				break
			walk += 1
		walk -= 1
		if walk - i > max_increase:
			max_increase = walk - i
		ls.append((walk - i, 0))
	else:
		while walk < n:
			if perms[walk] > perms[walk - 1]:
				break
			walk += 1
		walk -= 1
		if walk - i > max_decrease:
			max_decrease = walk - i
		ls.append((walk - i, 1))
	i = walk
max_hike = max(max_increase, max_decrease)
count = 0
for i in range(len(ls)):
	if ls[i][0] == max_hike:
		count += 1
if count >= 3:
	is_lost = True
elif count == 2:
	for i in range(len(ls) - 1):
		if ls[i][0] == max_hike:
			if ls[i + 1][0] == max_hike and ls[i][1] == 0 and (max_hike % 2 == 0):
				is_lost = False
				break
			else:
				is_lost = True
elif count == 1:
	is_lost = True
if not is_lost:
	print(1)
else:
	print(0)


import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

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

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	if N == 2:
		return 0
	left = [0]
	curr = 0
	M1 = 0
	for i in range(1, N):
		if A[i] > A[i - 1]:
			curr += 1
		else:
			curr = 0
		left.append(curr)
		M1 = max(M1, curr)
	right = [0]
	curr = 0
	M2 = 0
	for i in range(N - 2, -1, -1):
		if A[i] > A[i + 1]:
			curr += 1
		else:
			curr = 0
		right.append(curr)
		M2 = max(M2, curr)
	right.reverse()
	targ = max(M1, M2)
	curr = 0
	for i in range(N):
		if left[i] == targ or right[i] == targ:
			curr += 1
			idx = i
	if curr > 1:
		return 0
	op1 = right[idx]
	op2 = left[idx]
	other = min(op1, op2)
	min_block = targ - 1 ^ targ % 2
	if min_block >= other:
		return 0
	return 1
print(solve())


n = int(input())
pp = list(map(int, input().split()))
mx = 0
cnt = 0
for i in range(1, n - 1):
	if pp[i] > pp[i - 1] and pp[i] > pp[i + 1]:
		for j in range(i - 1, -1, -1):
			if pp[j] > pp[j + 1]:
				break
		for k in range(i + 1, n):
			if pp[k] > pp[k - 1]:
				break
		if pp[j] > pp[j + 1]:
			j += 1
		if pp[k] > pp[k - 1]:
			k -= 1
		j = i - j
		k = k - i
		if j == k and j & 1 == 0:
			if j > mx:
				mx = j
				cnt = 1
			elif j == mx:
				cnt += 1
ok = cnt == 1
mxinccnt = mxinc = cnt = 0
for (x, y) in zip(pp, pp[1:]):
	if y > x:
		cnt += 1
		if cnt > mxinc:
			mxinc = cnt
			mxinccnt = 1
		elif cnt == mxinc:
			mxinccnt += 1
	else:
		cnt = 0
cnt = 0
for (y, x) in zip(reversed(pp[:-1]), reversed(pp)):
	if y > x:
		cnt += 1
		if cnt > mxinc:
			mxinc = cnt
			mxinccnt = 1
		elif cnt == mxinc:
			mxinccnt += 1
	else:
		cnt = 0
print(1 if ok and (mxinc < mx or (mxinc == mx and mxinccnt == 2)) else 0)


import sys
input = sys.stdin.readline
import math
import copy
n = int(input())
p = list(map(int, input().split()))
up = []
down = []
i = 0
if p[1] > p[0]:
	None
else:
	while p[i + 1] < p[i]:
		i += 1
		if i == n - 1:
			exit(print(0))
up_num = 0
down_num = 0
for j in range(n - 1 - i):
	if p[j + i + 1] > p[j + i]:
		if down_num != 0:
			down.append(down_num)
			down_num = 0
		up_num += 1
	else:
		if up_num != 0:
			up.append(up_num)
			up_num = 0
		down_num += 1
if down_num != 0:
	down.append(down_num)
if len(up) == 0 or len(down) == 0:
	exit(print(0))
lim = max(max(up), max(down), up_num, i)
if i == lim or up_num == lim:
	exit(print(0))
ans = 0
for j in range(len(up)):
	if max(up[j], down[j]) == lim and up[j] == down[j] and (lim % 2 == 0):
		ans += 1
if ans >= 2:
	ans = 0
print(ans)


import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
x = [*map(int, input().split())]
m = n - 1
i = 0
a = b = 0
top = []
bot = set()
t = 0
while i < m:
	if x[i] > x[i + 1]:
		a = i
		while i < m and x[i] > x[i + 1]:
			i += 1
		a = i - a
		top.append((b, a))
	else:
		b = i
		while i < m and x[i] < x[i + 1]:
			i += 1
		b = i - b
		bot.add((a, b))
	t = max(t, a, b)
y = Counter()
for (a, b) in top:
	if a != b or a % 2:
		continue
	y[a] += 1
print(1 if y and y[t] == 1 and ((t, t) not in bot) else 0)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	P = list(map(int, input().split()))
	L = [0] * N
	R = [0] * N
	for i in range(1, N):
		if P[i] > P[i - 1]:
			L[i] = L[i - 1] + 1
	for i in range(N - 2, -1, -1):
		if P[i] > P[i + 1]:
			R[i] = R[i + 1] + 1
	ma_L = max(L)
	ma_R = max(R)
	ma = max(ma_L, ma_R)
	flg = 0
	for i in range(N):
		if L[i] == R[i] == ma:
			flg += 1
		elif L[i] == ma or R[i] == ma:
			flg = 2
	if ma & 1:
		flg = 2
	if flg == 1:
		print(1)
	else:
		print(0)
main()


import collections
n = int(input())
nums = [int(s) for s in input().split()]
queue = []
up = down = 0
for i in range(1, len(nums)):
	if nums[i] > nums[i - 1]:
		if down > 0:
			queue.append(-down)
			down = 0
			up = 1
		else:
			up += 1
	elif up > 0:
		queue.append(up)
		up = 0
		down = 1
	else:
		down += 1
if up > 0:
	queue.append(up)
if down > 0:
	queue.append(-down)
c = collections.Counter(queue)
m = max(c)
if m == -min(c) and c[m] == 1 and (c[-m] == 1) and (queue.index(m) + 1 == queue.index(-m)) and (m % 2 == 0):
	print(1)
else:
	print(0)


n = int(input())
p = list(map(int, input().split()))
(h1, h2) = ([0] * n, [0] * n)
for i in range(1, n):
	if p[i] > p[i - 1]:
		h1[i] = h1[i - 1] + 1
for i in range(n - 2, -1, -1):
	if p[i] > p[i + 1]:
		h2[i] = h2[i + 1] + 1
m = max(max(h1), max(h2))
(two, one) = (0, h1.count(m) + h2.count(m))
for i in range(n):
	if h1[i] == m and h2[i] == m:
		two += 1
if two == 1 and one == 2 and (m % 2 == 0):
	print(1)
else:
	print(0)


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
	n = inn()
	a = ina()
	inc = [1] * n
	rinc = inc[:]
	for (i, v) in enumerate(a):
		if i:
			if a[i - 1] < a[i]:
				inc[i] = 1 + inc[i - 1]
			else:
				inc[i] = 1
	b = a[::-1]
	for (i, v) in enumerate(b):
		if i:
			if b[i - 1] < b[i]:
				rinc[i] = 1 + rinc[i - 1]
			else:
				rinc[i] = 1
	rinc = rinc[::-1]
	m = max(inc)
	m = max(m, max(rinc))
	c = 0
	for i in inc:
		c += i == m
	for i in rinc:
		c += i == m
	if c > 2:
		print(0)
	elif c == 1:
		print(0)
	else:
		for i in range(n):
			if m % 2 == 1 and inc[i] == rinc[i] and (inc[i] == m):
				print(1)
				return
		print(0)

def main():
	t = 1
	for _ in range(t):
		solve()
main()


import sys
from math import sqrt
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
i = 0
ans = 1
tot = 1
while i + 1 < n:
	t1 = 1
	while i + 1 < n and a[i + 1] > a[i]:
		t1 += 1
		i += 1
	t2 = 1
	while i + 1 < n and a[i + 1] < a[i]:
		t2 += 1
		i += 1
	if ans < t1 or ans < t2:
		ans = max(ans, t1, t2)
		tot = min(t1, t2)
	elif ans == t1 or ans == t2:
		tot = 0
if ans % 2 and tot == ans:
	print(1)
else:
	print(0)


import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int, input().split()))
R = [1] * n
L = [1] * n
for i in range(1, n):
	if P[i] > P[i - 1]:
		L[i] = L[i - 1] + 1
for i in range(n - 2, -1, -1):
	if P[i] > P[i + 1]:
		R[i] = R[i + 1] + 1
MAX = max(max(R), max(L))
ANS = 0
flagr = 0
flagl = 0
for i in range(n):
	if R[i] == L[i] == MAX and MAX % 2 == 1:
		ANS += 1
	if R[i] == MAX:
		flagr += 1
	if L[i] == MAX:
		flagl += 1
if ANS == 1 and flagr == 1 and (flagl == 1):
	print(1)
else:
	print(0)


from itertools import groupby
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	p = list(map(int, input().split()))
	q = []
	for i in range(n - 1):
		if p[i + 1] > p[i]:
			q.append(1)
		else:
			q.append(-1)
	group = groupby(q)
	grad = []
	keys = []
	for (k, g) in group:
		g = list(g)
		grad.append(len(g))
		keys.append(k)
	grad_max = max(grad)
	c = grad.count(grad_max)
	ans = -1
	if c > 2:
		ans = 0
	elif c == 2:
		for i in range(len(grad)):
			if grad[i] == grad_max:
				if grad[i + 1] == grad_max and keys[i] == 1:
					if grad_max % 2 == 0:
						ans = 1
					else:
						ans = 0
				else:
					ans = 0
				break
	else:
		ans = 0
	print(ans)
main()


from sys import stdin, stdout
from collections import defaultdict
import math

def main():
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	if n < 4:
		stdout.write('0\n')
		return
	peak_pos = []
	for i in range(1, n - 1):
		if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
			peak_pos.append(i)
	if len(peak_pos) == 0:
		stdout.write('0\n')
		return
	mx = -1
	(mx_l, mx_r) = (-1, -1)
	peak_cnt = defaultdict(int)
	for peak in peak_pos:
		long_left = 0
		l = peak - 1
		while l >= 0 and arr[l] < arr[l + 1]:
			long_left += 1
			l -= 1
		r = peak + 1
		long_right = 0
		while r < n and arr[r] < arr[r - 1]:
			long_right += 1
			r += 1
		longest = max(long_left, long_right)
		peak_cnt[longest] += 1
		if longest > mx:
			mx = longest
			mx_l = long_left
			mx_r = long_right
	longest = max(mx_l, mx_r)
	if peak_cnt[longest] > 1:
		stdout.write('0\n')
		return
	left_p = 0
	for i in range(1, n - 1):
		if arr[i - 1] > arr[i]:
			left_p += 1
		else:
			break
	left_r = 0
	for i in range(n - 2, -1, -1):
		if arr[i + 1] > arr[i]:
			left_r += 1
		else:
			break
	if left_p >= longest or left_r >= longest:
		stdout.write('0\n')
		return
	if mx_l == mx_r and mx_l % 2 == 0:
		stdout.write('1\n')
	else:
		stdout.write('0\n')
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	p = list(map(int, input().split()))
	maxIncreasing = 0
	maxDecreasing = 0
	currentIncreasingCount = 1
	currentDecreasingCount = 1
	ansL = []
	bimodalMax = [False] * n
	bimodalMin = [False] * n
	for i in range(1, n):
		if p[i] > p[i - 1]:
			currentIncreasingCount += 1
			if currentDecreasingCount != 1:
				if ansL and ansL[-1] == currentDecreasingCount:
					bimodalMax[currentDecreasingCount - 1] = True
				ansL.append(currentDecreasingCount)
			currentDecreasingCount = 1
		else:
			currentDecreasingCount += 1
			if currentIncreasingCount != 1:
				if ansL and ansL[-1] == currentIncreasingCount:
					bimodalMin[currentIncreasingCount - 1] = True
				ansL.append(currentIncreasingCount)
			currentIncreasingCount = 1
	if currentIncreasingCount != 1:
		if ansL and ansL[-1] == currentIncreasingCount:
			bimodalMin[currentIncreasingCount - 1] = True
		ansL.append(currentIncreasingCount)
	if currentDecreasingCount != 1:
		if ansL and ansL[-1] == currentDecreasingCount:
			bimodalMax[currentDecreasingCount - 1] = True
		ansL.append(currentDecreasingCount)
	ansL.sort(reverse=True)
	if len(ansL) > 1 and ansL[0] == ansL[1] and bimodalMax[ansL[0] - 1]:
		ansL[1] -= 1
	ansL.append(ansL[0] // 2)
	ansL.sort(reverse=True)
	if ansL[0] == 2:
		print(0)
		return
	if bimodalMax[ansL[0] - 1] and ansL[1] != ansL[0]:
		print(ansL[0] % 2)
	else:
		print(0)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from collections import Counter, defaultdict

def load_sys():
	return sys.stdin.readlines()

def load_local():
	with open('input.txt', 'r') as f:
		input = f.readlines()
	return input

def f(n, arr):
	(l, c) = (0, 0)
	last_incr = 0
	cur = 0
	for i in range(1, len(arr)):
		incr = arr[i] - arr[i - 1]
		if last_incr == 0:
			cur = 2
		elif last_incr > 0:
			if incr > 0:
				cur += 1
			else:
				if l < cur:
					l = cur
					c = 1
				elif l == cur:
					c += 1
				cur = 2
		elif incr < 0:
			cur += 1
		else:
			if l < cur:
				l = cur
				c = 1
			elif l == cur:
				c += 1
			cur = 2
		last_incr = incr
	if cur == l:
		c += 1
	if cur > l:
		(l, c) = (cur, 1)
	if c != 2 or l % 2 == 0:
		return 0
	(rising, dropping) = (False, False)
	(seg1, seg2) = (0, 0)
	for i in range(1, len(arr)):
		if not rising and (not dropping):
			if arr[i] > arr[i - 1]:
				seg1 = 2
				rising = True
		elif rising and (not dropping):
			if arr[i] > arr[i - 1]:
				seg1 += 1
			else:
				seg2 = 2
				dropping = True
		elif rising and dropping:
			if arr[i] < arr[i - 1]:
				seg2 += 1
			else:
				if seg1 == l and seg2 == l:
					return 1
				seg1 = 2
				seg2 = 0
				rising = True
				dropping = False
	if seg1 == l and seg2 == l:
		return 1
	return 0
input = load_sys()
n = int(input[0])
arr = [int(x) for x in input[1].split()]
print(f(n, arr))


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
n = int(Z())
p = [*map(int, Z().split())]
a = p[0]
r = []
s = c = t = m = 0
for i in range(1, n):
	if p[i] > a:
		ns = 1
	else:
		ns = -1
	if s == ns:
		c += 1
	else:
		if s < 0 and r[-1] == c and c % 2:
			if c == m:
				t = 0
			elif c > m:
				t = 1
				m = c
		r.append(c)
		c = 2
		s = ns
	a = p[i]
if s < 0 and r[-1] == c and c % 2:
	if c == m:
		t = 0
	elif c > m:
		t = 1
		m = c
r.append(c)
if max(r) > m:
	t = 0
elif r.count(m) > 2:
	t = 0
print(t)


import sys
Z = sys.stdin.readline
n = int(Z())
p = [*map(int, Z().split())]
a = p[0]
r = []
s = c = t = m = 0
for i in range(1, n):
	if p[i] > a:
		w = 1
	else:
		w = -1
	if s == w:
		c += 1
	else:
		if s < 0 and r[-1] == c and c % 2:
			if c == m:
				t = 0
			elif c > m:
				t = 1
				m = c
		r.append(c)
		c = 2
		s = w
	a = p[i]
if s < 0 and r[-1] == c and c % 2:
	if c == m:
		t = 0
	elif c > m:
		t = 1
		m = c
r.append(c)
if max(r) > m:
	t = 0
elif r.count(m) > 2:
	t = 0
print(t)


import sys

def input():
	return sys.stdin.readline().rstrip()
n = int(input())
p = list(map(int, input().split()))
a = [0] * n
b = [0] * n
for i in range(n - 1):
	if p[i] < p[i + 1]:
		a[i + 1] = a[i] + 1
for i in range(n - 1, 0, -1):
	if p[i - 1] > p[i]:
		b[i - 1] = b[i] + 1
x = max(max(a), max(b))
k = sum((x == i or x == j for (i, j) in zip(a, b)))
s = sum((x == i and x == j for (i, j) in zip(a, b)))
if k > 1 or s == 0 or x % 2:
	print(0)
else:
	print(1)


n = int(input())
a = list(map(int, input().split()))
new1 = [0]
mx = 0
new2 = [0] * n
for i in range(1, n):
	new1.append(new1[i - 1] + 1 if a[i] > a[i - 1] else 0)
	mx = max(mx, new1[i])
for i in range(n - 2, -1, -1):
	if a[i + 1] < a[i]:
		new2[i] = new2[i + 1] + 1
	mx = max(mx, new2[i])
ans = new1.count(mx) + new2.count(mx)
if ans == 2:
	flag = 0
	for i in range(n):
		if new1[i] == mx and new2[i] == mx:
			flag += 1
	if flag == 1:
		print('1') if mx % 2 == 0 else print('0')
	else:
		print('0')
else:
	print('0')


import sys
import math
from itertools import permutations
from bisect import bisect_left
import heapq
from collections import deque

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def isPal(s):
	return s == s[:][::-1]

def getMaxSorted(a):
	temp = 1
	m = 1
	for i in range(1, len(a) + 1):
		if i < len(a) and a[i] > a[i - 1]:
			temp += 1
		else:
			m = max(m, temp)
			temp = 1
	temp = 1
	for i in range(1, len(a) + 1):
		if i < len(a) and a[i] < a[i - 1]:
			temp += 1
		else:
			m = max(m, temp)
			temp = 1
	return m
n = II()
a = LI()
temp = 1
ind = -1
m = 1
ci = 0
for i in range(1, n + 1):
	if i < n and a[i] < a[i - 1]:
		temp += 1
	else:
		if temp > m:
			m = temp
			ind = ci
		temp = 1
		ci = i
ci = n - 1
temp = 1
for i in range(n - 2, -2, -1):
	if i >= 0 and a[i] < a[i + 1]:
		temp += 1
	else:
		if temp > m:
			m = temp
			ind = ci
		temp = 1
		ci = i
boo = True
if ind == 0 or ind == n - 1:
	boo = False
else:
	l = ind - 1
	while l >= 0 and a[l] < a[l + 1]:
		l -= 1
	r = ind + 1
	while r < n and a[r] < a[r - 1]:
		r += 1
	(x, y) = (min(ind - l, r - ind), max(ind - l, r - ind))
	if y <= getMaxSorted(a[:ind]) or y <= getMaxSorted(a[ind + 1:]):
		boo = False
	if y % 2 == 1:
		y -= 1
	if x <= y:
		boo = False
print(1 if boo else 0)


n = int(input())
data = list(map(int, input().split()))
process = []
flag = False
for i in range(1, len(data) - 1):
	if data[i] > data[i - 1] and data[i] > data[i + 1]:
		flag = True
		process.append([])
		index1 = i - 1
		index2 = i + 1
		while index1 >= 0 and data[index1] < data[index1 + 1]:
			index1 -= 1
		process[-1].append(index1 + 1)
		process[-1].append(i)
		while index2 < n and data[index2] < data[index2 - 1]:
			index2 += 1
		process[-1].append(index2 - 1)
if not flag:
	print(0)
	exit(0)
max_len = 0
max_len_b = max(process[0][0] + 1, n - process[-1][-1])
counter = 0
for i in range(len(process)):
	len1 = process[i][1] - process[i][0] + 1
	len2 = process[i][2] - process[i][1] + 1
	if len1 != len2 or len1 % 2 != 1:
		process[i] = []
		max_len_b = max(max_len_b, len1, len2)
	else:
		max_len = max(max_len, len1)
if max_len <= max_len_b:
	print(0)
else:
	for i in range(len(process)):
		if process[i]:
			if process[i][1] - process[i][0] + 1 == max_len:
				counter += 1
	if counter > 1:
		print(0)
	else:
		print(1)


a = int(input())
z = list(map(int, input().split()))
ans = []
cnt = 1
for i in range(1, len(z)):
	if z[i] > z[i - 1]:
		if i == 1:
			cnt += 1
			trend = 1
			continue
		if trend == 1:
			cnt += 1
		else:
			ans.append([cnt, 0])
			cnt = 2
			trend = 1
	else:
		if i == 1:
			cnt += 1
			trend = 0
			continue
		if trend == 0:
			cnt += 1
		else:
			ans.append([cnt, 1])
			cnt = 2
			trend = 0
from collections import *
ans.append([cnt, trend])
dl = defaultdict(int)
maxa = 0
for i in range(len(ans)):
	dl[ans[i][0]] += 1
	maxa = max(maxa, ans[i][0])
if dl[maxa] == 2 and maxa % 2 == 1:
	flag = 0
	for i in range(len(ans) - 1):
		if ans[i][0] == ans[i + 1][0] and ans[i][0] == maxa and (ans[i][1] == 1):
			flag = 1
			break
	if flag == 1:
		print('1')
		exit(0)
print(0)


n = int(input())
p = [int(x) for x in input().split()]
peaks = []
for i in range(1, n - 1):
	if p[i] > p[i - 1] and p[i] > p[i + 1]:
		peaks.append(i)
if len(peaks) == 0:
	print('0')
	exit()
peaksCount = []
bestCount = -1
beg = n
end = 0
for i in peaks:
	leftCount = 1
	rightCount = 1
	j = i - 1
	while j >= 0 and p[j] < p[j + 1]:
		j -= 1
		leftCount += 1
	beg = min(beg, j + 1)
	j = i + 1
	while j < n and p[j] < p[j - 1]:
		j += 1
		rightCount += 1
	end = max(end, j - 1)
	peaksCount.append((leftCount, rightCount))
	bestCount = max(bestCount, leftCount, rightCount)
hillLeft = beg + 1
hillRight = n - end
matchesBestCount = 0
m = -1
for (lc, rc) in peaksCount:
	if lc == bestCount or rc == bestCount:
		matchesBestCount += 1
		m = (lc, rc)
if matchesBestCount > 1 or bestCount <= max(hillLeft, hillRight):
	print('0')
	exit()
if m[0] % 2 == 1 and m[0] == m[1]:
	print('1')
	exit()
print(0)