In Chef's house there are N apples lying in a row on the floor. These apples are numbered from 1 (left most one) to N (right most one). The types of apples are also numbered by positive integers, and the type of apple i is Ti.
Chef has recently brought two trained dogs. Both of the dogs are too intelligent to know the smell of each type of apple. If Chef gives a dog an integer x, and releases it at one end of the row of apples, then the dog smells each apple one by one. Once the dog find an apple of type x, the dog picks the apple and back to Chef's room immidiately. If there is no apple of type x, then the dog will back without any apples.
Now Chef wants to eat two apples as soon as possible. Here the apples must have distinct types, and the sum of the types must be equal to K. Chef can release the dogs from either of the ends, namely, he can leave (both at left end) or (both at right end) or (one at left end and one at right end) and he can release them at the same time. The dogs take one second to smell each apple. However the dogs can run rapidly, so the time for moving can be ignored. What is the minimum time (in seconds) to get the desired apples from his dogs?

-----Input-----
The first line of input contains two space-separated integers N and K, denoting the number of apples and the required sum respectively. Then the next line contains N space-separated integers T1, T2, ..., TN, denoting the types of the apples.

-----Output-----
Print one integer describing the minimum number of seconds that Chef needs to wait till he gets the desired apples. If Chef cannot get the desired apples, then output "-1" without quotes.

-----Constraints-----
- 2 ≤ N ≤ 500000 (5 × 105)
- 1 ≤ K ≤ 1000000 (106)
- 1 ≤ Ti ≤ 1000000 (106)

-----Example-----
Sample Input 1:
5 5
2 4 3 2 1

Sample Output 1:
2

Sample Input 2:
5 5
2 4 9 2 5

Sample Output 2:
-1

-----Explanation-----
In the first example, if Chef leaves the first dog from left and gives it integer 4, and the second dog from right and gives it integer 1, then the first dog takes 2 seconds and the second dog takes 1 second to get the apples. Thus Chef needs to wait 2 seconds. In any other way, Chef can't get the desired apples in less than 2 seconds.
In the second example, Chef cannot get two apples such that the sum of their types is 5 so the answer is "-1".

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
(n, k) = map(int, input().split())
la = list(map(int, input().split()))
mini = 10 ** 18
from collections import defaultdict
hash = defaultdict(int)
for i in range(len(la)):
	z1 = i + 1
	z2 = n - i
	z = min(z1, z2)
	if la[i] in hash:
		hash[la[i]] = min(z, hash[la[i]])
	else:
		hash[la[i]] = z
for i in range(len(la)):
	z = k - la[i]
	if z in hash and z != la[i]:
		ans = max(hash[z], hash[la[i]])
		mini = min(mini, ans)
if mini == 10 ** 18:
	print(-1)
else:
	print(mini)


def main():
	(N, K) = map(int, input().split())
	Apples = [int(x) for x in input().split()]
	time = 0
	distinct_apples_condition = None if K & 1 else K >> 1
	already_found = [False] * K
	for i in range((N >> 1) + 1):
		time += 1
		for k in (Apples[i], Apples[N - i - 1]):
			if k < K and k != distinct_apples_condition:
				if already_found[K - k - 1]:
					return time
				already_found[k - 1] = True
	return -1
print(main())


import sys
(n, k) = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
R = {}
L = {}
for i in range(n):
	if A[i] not in L:
		L[A[i]] = i
for i in range(n - 1, -1, -1):
	if A[i] not in R:
		R[A[i]] = n - 1 - i
best = 10 ** 10
for i in range(n):
	x = k - A[i]
	if x <= 0 or x == A[i] or x not in L:
		continue
	m = min(L[x], R[x])
	h = min(i + 1, n - i)
	best = min(best, max(h, m + 1))
if best != 10 ** 10:
	print(best)
else:
	print(-1)


import bisect, sys
MAX = 1000000
(N, K) = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
(L, R) = ({}, {})
for (i, x) in enumerate(T):
	if x not in L:
		L[x] = i
	R[x] = i
T = frozenset(T)
min_idx = N
for x in sorted(T):
	if 2 * x >= K:
		break
	elif K - x in T:
		min_idx = min(min_idx, max(L[x] + 1, L[K - x] + 1))
		min_idx = min(min_idx, max(L[x] + 1, N - R[K - x]))
		min_idx = min(min_idx, max(N - R[x], N - R[K - x]))
		min_idx = min(min_idx, max(N - R[x], L[K - x] + 1))
print(min_idx if min_idx < N else -1)


import sys
input = sys.stdin.readline
Max = 10 ** 6 + 7
(n, k) = map(int, input().split())
l1 = list(map(int, input().split()))
l = [Max for i in range(Max)]
for i in range(n):
	l[l1[i]] = min(l[l1[i]], min(i + 1, n - i))
if k % 2 == 0:
	l[k // 2] = Max
ans = Max
for i in range(k + 1):
	if l[i] != Max and l[k - i] != Max:
		ans = min(ans, max(l[i], l[k - i]))
if ans != Max:
	print(ans)
else:
	print(-1)


temp = list(map(int, input().split()))
n = temp[0]
k = temp[1]
a = list(map(int, input().split()))
minn = 10 ** 8
maxx = -1
for i in range(n):
	if a[i] > maxx:
		maxx = a[i]
	if a[i] < minn:
		minn = a[i]
hash = []
l = 0
pos = []
i = minn
while i <= maxx:
	hash.append(0)
	l += 1
	pos.append(-5)
	i += 1
for i in range(n):
	x = a[i] - minn
	hash[x] += 1
	if pos[x] == -5:
		pos[x] = min(i, n - 1 - i)
	else:
		pos[x] = min(pos[x], i, n - 1 - i)
ans = ''
for i in range(l):
	if hash[i] == 0:
		continue
	else:
		val1 = i + minn
		if val1 >= k:
			continue
		else:
			val2 = k - val1
			index2 = val2 - minn
			if val1 == val2 or index2 < 0 or index2 >= l or (hash[index2] == 0):
				continue
			elif ans == '':
				ans = max(pos[i], pos[index2])
			elif ans > max(pos[i], pos[index2]):
				ans = max(pos[i], pos[index2])
if ans == '':
	print(-1)
else:
	print(ans + 1)


(n, k) = [int(word) for word in input().split()]
t = [int(word) for word in input().split()]
infty = 1000000000
mindist = [infty] * 1000001
for i in range(n):
	mindist[t[i]] = min(mindist[t[i]], i + 1, n - i)
mintime = infty
for i in range(1, (k + 1) // 2):
	time = max(mindist[i], mindist[k - i])
	if time < mintime:
		mintime = time
if mintime == infty:
	print('-1')
else:
	print(mintime)


(n, k) = map(int, input().split())
A = map(int, input().split())
(D, dist) = ({}, {})
for (i, a) in enumerate(A):
	D[a] = 0
	dist[a] = min(dist.get(a, float('inf')), i, n - i - 1)
hk = k / 2
c = float('inf')
for a in D:
	if a < hk:
		b = k - a
		if b in D:
			c = min(c, max(dist[a], dist[b]))
print(-1 if c == float('inf') else c + 1)


import bisect, sys
MAX = 1000000
(N, K) = list(map(int, sys.stdin.readline().split()))
T = {}
for (i, x) in enumerate(map(int, sys.stdin.readline().split())):
	steps = min(i + 1, N - i)
	if x in T:
		T[x] = min(T[x], steps)
	else:
		T[x] = steps
min_steps = N
for x in sorted(T):
	if 2 * x >= K:
		break
	elif K - x in T:
		min_steps = min(min_steps, max(T[x], T[K - x]))
print(min_steps if min_steps < N else -1)


import math
(trees, sum) = map(int, input().split(' '))
forest = tuple(map(int, input().split(' ')))
middle = math.floor(trees / 2)
halfsum = sum / 2
visited = set()
printed = False
for i in range(middle):
	j = -1 - i
	if forest[i] in visited or forest[j] in visited or (forest[i] != forest[j] and forest[i] + forest[j] == sum):
		print(i + 1)
		printed = True
		break
	else:
		if forest[i] != halfsum and forest[i] < sum:
			visited.add(sum - forest[i])
		if forest[j] != halfsum and forest[j] < sum:
			visited.add(sum - forest[j])
		continue
if not printed:
	if middle * 2 < trees and forest[middle] in visited:
		print(middle + 1)
	else:
		print(-1)


(n, k) = map(int, input().split())
z = input().split()
t = list(map(int, z[:n]))
s = [(t[e], min(e + 1, n - e)) for e in range(n)]
s.sort()
mind = n
lo = 0
hi = n - 1
while hi > lo:
	tot = s[hi][0] + s[lo][0]
	if tot == k:
		if s[hi][0] == s[lo][0]:
			break
		while s[hi - 1][0] == s[hi][0]:
			hi -= 1
		dist = max(s[hi][1], s[lo][1])
		if mind > dist:
			mind = dist
	if tot >= k:
		hi -= 1
	else:
		lo += 1
print(mind if mind < n else -1)