The life goes up and down, just like nice sequences. Sequence t_1, t_2, ..., t_{n} is called nice if the following two conditions are satisfied:   t_{i} < t_{i} + 1 for each odd i < n;  t_{i} > t_{i} + 1 for each even i < n. 

For example, sequences (2, 8), (1, 5, 1) and (2, 5, 1, 100, 99, 120) are nice, while (1, 1), (1, 2, 3) and (2, 5, 3, 2) are not.

Bear Limak has a sequence of positive integers t_1, t_2, ..., t_{n}. This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices i < j and swap elements t_{i} and t_{j} in order to get a nice sequence. Count the number of ways to do so. Two ways are considered different if indices of elements chosen for a swap are different.


-----Input-----

The first line of the input contains one integer n (2 ≤ n ≤ 150 000) — the length of the sequence.

The second line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 150 000) — the initial sequence. It's guaranteed that the given sequence is not nice.


-----Output-----

Print the number of ways to swap two elements exactly once in order to get a nice sequence.


-----Examples-----
Input
5
2 8 4 7 7

Output
2

Input
4
200 150 100 50

Output
1

Input
10
3 2 1 4 1 4 1 4 1 4

Output
8

Input
9
1 2 3 4 5 6 7 8 9

Output
0



-----Note-----

In the first sample, there are two ways to get a nice sequence with one swap:   Swap t_2 = 8 with t_4 = 7.  Swap t_1 = 2 with t_5 = 7. 

In the second sample, there is only one way — Limak should swap t_1 = 200 with t_4 = 50.

Difficulty: HARD
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	if not n & 1:
		l.append(0)
	l.append(150001)
	(a, b, fails, res) = (0, 150001, [], 0)
	for (i, c) in enumerate(l, -1):
		if i & 1:
			if a >= b or b <= c:
				if len(fails) > 5:
					print(0)
					return
				fails.append(i)
		elif a <= b or b >= c:
			if len(fails) > 5:
				print(0)
				return
			fails.append(i)
		(a, b) = (b, c)
	ff = fails + [0]
	for i in fails:
		a = l[i]
		for j in range(n):
			(l[i], l[j], ff[-1]) = (l[j], a, j)
			if all((l[b - 1] < l[b] > l[b + 1] if b & 1 else l[b - 1] > l[b] < l[b + 1] for b in ff)):
				res += 1 if j in fails else 2
			l[j] = l[i]
		l[i] = a
	print(res // 2)
main()


n = int(input())
t = [int(d) for d in input().split()]
m = 0
ind = [0, 0]
nb = [0, 0]
res = -1

def mis(i, v):
	if i == n - 1:
		return False
	if i == -1:
		return False
	if v >= t[i + 1] and i % 2 == 0 or (v <= t[i + 1] and i % 2 == 1):
		return True
	return False

def miso(i, v):
	if i == n - 1:
		return False
	if i == -1:
		return False
	if t[i] >= v and i % 2 == 0 or (t[i] <= v and i % 2 == 1):
		return True
	return False
for i in range(n - 1):
	if mis(i, t[i]):
		if m == 2:
			res = 0
			break
		if nb[m] > 0:
			nb[m] = nb[m] + 1
		else:
			ind[m] = i
			nb[m] = 2
		if i == n - 2 and nb[m] > 0:
			m = m + 1
	else:
		if m == 2:
			continue
		if nb[m] > 0:
			m = m + 1

def switch(i, j):
	if i == j - 1:
		(t[i], t[j]) = (t[j], t[i])
		bol = not (mis(i, t[i]) or miso(i - 1, t[i]) or mis(j, t[j]) or miso(j - 1, t[j]))
		(t[i], t[j]) = (t[j], t[i])
		return bol
	return not (mis(i, t[j]) or miso(i - 1, t[j]) or mis(j, t[i]) or miso(j - 1, t[i]))
if res == 0 or nb[0] > 5 or nb[1] > 5:
	print(0)
elif (nb[0] == 4 or nb[0] == 5) and m == 2:
	print(0)
elif (nb[1] == 4 or nb[1] == 5) and m == 2:
	print(0)
else:
	res = 0
	i = ind[0]
	j = ind[1]
	if nb[0] == 5:
		if switch(i + 1, i + 3):
			res = 1
	elif nb[0] == 4:
		res = int(switch(i + 1, i + 2)) + int(switch(i + 1, i + 3)) + int(switch(i, i + 2))
	elif m == 2:
		if switch(i + 1, j + 1):
			res = res + 1
		if nb[0] == 2 and switch(i, j + 1):
			res = res + 1
		if nb[1] == 2 and switch(i + 1, j):
			res = res + 1
		if nb[0] == 2 and nb[1] == 2 and switch(i, j):
			res = res + 1
	else:
		for k in range(n):
			if k != i + 1 and switch(min(i + 1, k), max(i + 1, k)):
				res = res + 1
			if nb[0] == 2 and k != i and (k != i + 1) and switch(min(i, k), max(i, k)):
				res = res + 1
	print(res)


def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	if not n & 1:
		l.append(0)
	l.append(150001)
	(a, b, fails, tmp, res) = (0, 150001, [], [], 0)
	for (i, c) in enumerate(l, -1):
		if i & 1:
			if a >= b or b <= c:
				if len(fails) > 5:
					print(0)
					return
				fails.append(i)
		elif a <= b or b >= c:
			if len(fails) > 5:
				print(0)
				return
			fails.append(i)
		(a, b) = (b, c)
	for b in fails:
		tmp.append('><'[b & 1] if b - a == 1 else 'and ')
		tmp.append('l[{:n}]'.format(b))
		a = b
	check = compile(''.join(tmp[1:]), '<string>', 'eval')
	for i in fails:
		a = l[i]
		for j in range(0, n, 2):
			(l[i], l[j]) = (l[j], a)
			if l[j - 1] > a < l[j + 1] and eval(check):
				res += 1 if j in fails else 2
			l[j] = l[i]
		for j in range(1, n, 2):
			(l[i], l[j]) = (l[j], a)
			if l[j - 1] < a > l[j + 1] and eval(check):
				res += 1 if j in fails else 2
			l[j] = l[i]
		l[i] = a
	print(res // 2)

def __starting_point():
	main()
__starting_point()


n = int(input())
t = list(map(int, input().split()))
t = [-1] + t
badIdx = []
nice = []

def getBadIdx():
	for i in range(1, n):
		if i % 2 == 0 and t[i] <= t[i + 1] or (i % 2 == 1 and t[i] >= t[i + 1]):
			badIdx.append((i, i + 1))

def checkBad(k):
	if k <= n - 1 and (k % 2 == 0 and t[k] <= t[k + 1] or (k % 2 == 1 and t[k] >= t[k + 1])) or (k - 1 >= 1 and ((k - 1) % 2 == 0 and t[k - 1] <= t[k] or ((k - 1) % 2 == 1 and t[k - 1] >= t[k]))):
		return True
	for (i, j) in badIdx:
		if i % 2 == 0 and t[i] <= t[j] or (i % 2 == 1 and t[i] >= t[j]):
			return True
	return False

def swap(i, j):
	ith = t[i]
	t[i] = t[j]
	t[j] = ith
getBadIdx()
if len(badIdx) > 4:
	print(0)
else:
	(i, j) = badIdx[0]
	for k in range(1, n + 1):
		if i != k and t[i] != t[k]:
			swap(i, k)
			if not checkBad(k):
				nice.append((i, k))
				swap(i, k)
			else:
				swap(i, k)
		if j != k and t[j] != t[k]:
			swap(j, k)
			if not checkBad(k):
				nice.append((j, k))
				swap(j, k)
			else:
				swap(j, k)
	print(len(set([tuple(sorted(t)) for t in nice])))


def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	if not n & 1:
		l.append(0)
	l.append(150001)
	(i, b, c, fails0, fails1) = (0, 0, 150001, [], [])
	try:
		while True:
			(a, b, c) = (b, c, l[i])
			if a >= b or b <= c:
				if len(fails0) + len(fails1) > 5:
					print(0)
					return
				fails1.append(i - 1)
			i += 1
			(a, b, c) = (b, c, l[i])
			if a <= b or b >= c:
				if len(fails0) + len(fails1) > 5:
					print(0)
					return
				fails0.append(i - 1)
			i += 1
	except IndexError:
		(fails, res) = (fails0 + fails1, 0)
	for i in fails:
		a = l[i]
		for j in range(n):
			f = fails1 if j & 1 else fails0
			f.append(j)
			(l[i], l[j]) = (l[j], a)
			if all((l[b - 1] > l[b] < l[b + 1] for b in fails0)) and all((l[b - 1] < l[b] > l[b + 1] for b in fails1)):
				res += 1 if j in fails else 2
			l[j] = l[i]
			del f[-1]
		l[i] = a
	print(res // 2)
main()


def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	if not n & 1:
		l.append(0)
	l.append(150001)
	(a, i, j, fails) = (l[0], 0, 1, set())
	try:
		while True:
			b = l[j]
			if a >= b:
				fails.add(i)
				fails.add(j)
				if len(fails) > 6:
					break
			i += 2
			a = l[i]
			if a >= b:
				fails.add(i)
				fails.add(j)
				if len(fails) > 6:
					break
			j += 2
		print(0)
		return
	except IndexError:
		(tmp, res) = ([], 0)
	for b in sorted(fails):
		tmp.append('><'[b & 1] if b - a == 1 else 'and ')
		tmp.append('l[{:n}]'.format(b))
		a = b
	check = compile(''.join(tmp[1:]), '<string>', 'eval')
	for i in fails:
		a = l[i]
		for j in fails:
			(l[i], l[j]) = (l[j], a)
			if eval(check):
				res -= 1
			l[j] = l[i]
		for j in range(0, n, 2):
			(l[i], l[j]) = (l[j], a)
			if l[j - 1] > a < l[j + 1] and eval(check):
				res += 2
			l[j] = l[i]
		for j in range(1, n, 2):
			(l[i], l[j]) = (l[j], a)
			if l[j - 1] < a > l[j + 1] and eval(check):
				res += 2
			l[j] = l[i]
		l[i] = a
	print(res // 2)

def __starting_point():
	main()
__starting_point()


def get_bit(diff, i):
	return 1 if i % 2 == 1 and diff <= 0 or (i % 2 == 0 and diff >= 0) else 0

def swap_(i, j, a):
	temp = a[i]
	a[i] = a[j]
	a[j] = temp

def swap(i, j, n, a, mask, S):
	change = 0
	swap_(i, j, a)
	set_index = set([i, j])
	if i < n - 1:
		set_index.add(i + 1)
	if j < n - 1:
		set_index.add(j + 1)
	for index in set_index:
		if index > 0:
			diff = a[index] - a[index - 1]
			bit_ = get_bit(diff, index)
			change += bit_ - mask[index]
	swap_(i, j, a)
	if S + change == 0:
		return 1
	return 0
n = int(input())
a = list(map(int, input().split()))
diff = [-1] + [x - y for (x, y) in zip(a[1:], a[:-1])]
mask = [get_bit(diff[i], i) for i in range(n)]
S = sum(mask)
first = -1
for (i, x) in enumerate(mask):
	if x == 1:
		first = i
		break
cnt = 0
for second in range(n):
	if swap(first, second, n, a, mask, S) == 1:
		cnt += 1
	if first != 0 and swap(first - 1, second, n, a, mask, S) == 1:
		cnt += 1
if first != 0 and swap(first - 1, first, n, a, mask, S) == 1:
	cnt -= 1
print(cnt)


(n, m) = (int(input()), 150001)
p = [m] + list(map(int, input().split())) + [m * (n & 1)]
f = lambda i: p[i] >= p[i + 1] if i & 1 else p[i] <= p[i + 1]
h = lambda i, j: sum((f(k) for k in {i, i - 1, j, j - 1}))
t = [f(i) for i in range(n + 1)]
s = sum(t)
if s > 4:
	exit(print(0))
e = {i + 1 for i in range(n) if t[i] or t[i + 1]}

def g(i, j):
	(p[i], p[j]) = (p[j], p[i])
	t = h(i, j)
	(p[i], p[j]) = (p[j], p[i])
	return (i < j or (i > j and j not in e)) and h(i, j) - t == s
print(sum((g(i, j + 1) for i in e for j in range(n))))


3

def needs_rep(t, i):
	if i % 2 == 0:
		return t[i] >= t[i + 1]
	else:
		return t[i] <= t[i + 1]

def would_need_rep(t, i, j1, j2):
	n = len(t)
	if i < 0:
		return False
	if i >= n - 1:
		return False
	tj1 = t[j2]
	tj2 = t[j1]
	ti = t[i]
	if i == j1:
		ti = tj1
	if i == j2:
		ti = tj2
	ti1 = t[i + 1]
	if i + 1 == j1:
		ti1 = tj1
	if i + 1 == j2:
		ti1 = tj2
	if i % 2 == 0:
		return ti >= ti1
	else:
		return ti <= ti1

def main():
	n = int(input())
	t = [int(i) for i in input().split()]
	rep = []
	for i in range(n - 1):
		if needs_rep(t, i):
			rep.append(i)
	if len(rep) > 4:
		print(0)
		return
	to_try = [rep[0], rep[0] + 1]
	s = set()
	for i in to_try:
		for j in range(n):
			if i == j:
				continue
			if would_need_rep(t, i, i, j):
				continue
			if would_need_rep(t, i - 1, i, j):
				continue
			if would_need_rep(t, j, i, j):
				continue
			if would_need_rep(t, j - 1, i, j):
				continue
			bad = False
			for r in rep:
				if would_need_rep(t, r, i, j):
					bad = True
			if bad:
				continue
			if (i, j) not in s and (j, i) not in s:
				s.add((i, j))
	print(len(s))

def __starting_point():
	main()
__starting_point()