In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
 
Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].


Example 2:
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].


Example 3:
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].


Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

 



Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        

Solutions:
class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		prior_fruit = tree[0]
		prior_fruit_counter = 0
		fruits_in_basket = [tree[0]]
		fruits_in_basket_counter = 0
		max_fib = -1
		for fruit in tree:
			if prior_fruit == fruit:
				prior_fruit_counter += 1
				fruits_in_basket_counter += 1
			elif prior_fruit != fruit:
				if fruit in fruits_in_basket:
					fruits_in_basket_counter += 1
				else:
					(fruits_in_basket, fruits_in_basket_counter) = ([prior_fruit, fruit], prior_fruit_counter + 1)
				(prior_fruit, prior_fruit_counter) = (fruit, 1)
			if fruits_in_basket_counter > max_fib:
				max_fib = fruits_in_basket_counter
		return max_fib


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		best_so_far = start = 0
		fruit_1 = fruit_2 = fruit_1_last_index = fruit_2_last_index = None
		for end in range(len(tree)):
			if fruit_1 is None:
				fruit_1 = tree[end]
				fruit_1_last_index = end
			elif fruit_2 is None and tree[end] != fruit_1:
				fruit_2 = tree[end]
				fruit_2_last_index = end
			elif tree[end] == fruit_1:
				fruit_1_last_index = end
			elif tree[end] == fruit_2:
				fruit_2_last_index = end
			else:
				best_so_far = max(best_so_far, end - start)
				if fruit_1_last_index < fruit_2_last_index:
					start = fruit_1_last_index + 1
					fruit_1 = tree[end]
					fruit_1_last_index = end
				else:
					start = fruit_2_last_index + 1
					fruit_2 = tree[end]
					fruit_2_last_index = end
		return max(best_so_far, len(tree) - start)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		q = []
		ans = -99999999999
		s = 0
		e = s
		while e < len(tree):
			if tree[e] not in q:
				if len(q) < 2:
					q.append(tree[e])
				else:
					if e - s > ans:
						ans = e - s
					i = e - 1
					while tree[i] == tree[e - 1] and i > -1:
						i -= 1
					s = i + 1
					q.clear()
					q.append(tree[s])
					q.append(tree[e])
			e += 1
		if e - s > ans:
			ans = e - s
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		tran_ptr = 0
		maxlist = []
		while True:
			scan_ptr = tran_ptr
			count = 0
			types = []
			while True:
				if tree[scan_ptr] in types:
					count += 1
				elif len(types) == 0:
					types.append(tree[scan_ptr])
					count += 1
				elif len(types) == 1:
					tran_ptr = scan_ptr
					types.append(tree[scan_ptr])
					count += 1
				else:
					break
				scan_ptr += 1
				if scan_ptr == len(tree):
					break
			maxlist.append(count)
			if scan_ptr == len(tree):
				break
		return max(maxlist)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		window = collections.Counter()
		ans = 0
		left = 0
		for right in range(len(tree)):
			window[tree[right]] += 1
			while len(window) > 2:
				window[tree[left]] -= 1
				if window[tree[left]] == 0:
					del window[tree[left]]
				left += 1
			ans = max(ans, sum(window.values()))
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxi = 0
		if len(tree) == 1:
			return 1
		l = []
		s = set()
		for i in range(len(tree)):
			l.append(tree[i])
			s.add(tree[i])
			if len(s) > 2:
				while len(set(l)) > 2:
					l = l[1:]
			maxi = max(maxi, len(l))
		return maxi


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = 0
		max_elem_count = 0
		window = {}
		start = 0
		l = len(tree)
		for end in range(l):
			if tree[end] in window:
				window[tree[end]] += 1
			else:
				window[tree[end]] = 1
			max_elem_count = max(max_elem_count, window[tree[end]])
			while len(window) > 2:
				window[tree[start]] -= 1
				if window[tree[start]] == 0:
					window.pop(tree[start])
				start += 1
			res = max(res, end - start + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		import collections
		fruits = collections.defaultdict(int)
		max_len = 0
		front = back = 0
		while back < len(tree):
			if len(list(fruits.keys())) <= 2:
				fruits[tree[back]] += 1
				back += 1
			else:
				fruits[tree[front]] -= 1
				if fruits[tree[front]] == 0:
					del fruits[tree[front]]
				front += 1
			if len(list(fruits.keys())) <= 2:
				max_len = max(max_len, back - front)
		return max_len


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		max_count = 1
		basket = {tree[0]: 1}
		i = 0
		for j in range(1, len(tree)):
			basket[tree[j]] = basket.get(tree[j], 0) + 1
			while len(basket) > 2:
				basket[tree[i]] = basket.get(tree[i], 0) - 1
				if basket[tree[i]] == 0:
					basket.pop(tree[i])
				i += 1
			curr_count = sum(basket.values())
			max_count = max(max_count, curr_count)
		return max_count


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		p1 = 0
		p2 = 0
		counter = 0
		mx = 0
		mmap = {}
		uniq = set()
		while p2 < len(tree):
			if len(uniq) > 2:
				mmap[tree[p1]] -= 1
				if mmap[tree[p1]] == 0:
					uniq.remove(tree[p1])
				p1 += 1
			else:
				if tree[p2] in mmap:
					mmap[tree[p2]] += 1
				else:
					mmap[tree[p2]] = 1
				uniq.add(tree[p2])
				if len(uniq) <= 2:
					counter = p2 - p1 + 1
				mx = max(mx, counter)
				p2 += 1
		return mx


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(set(tree)) <= 2:
			return len(tree)
		res = cur = count_b = a = b = 0
		for c in tree:
			cur = cur + 1 if c in (a, b) else count_b + 1
			count_b = count_b + 1 if c == b else 1
			if b != c:
				(a, b) = (b, c)
			res = max(res, cur)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		fruit_types = collections.Counter()
		max_fruit = 0
		start_idx = 0
		end_idx = 0
		while end_idx < len(tree):
			fruit_types[tree[end_idx]] += 1
			while len(fruit_types) > 2:
				fruit_types[tree[start_idx]] -= 1
				if fruit_types[tree[start_idx]] == 0:
					del fruit_types[tree[start_idx]]
				start_idx += 1
			max_fruit = max(max_fruit, sum(fruit_types.values()))
			end_idx += 1
		return max_fruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		total_fruits = collections.defaultdict(int)
		unique_baskets = 0
		max_fruit_types = 0
		start = 0
		for end in range(len(tree)):
			cur_fruit = tree[end]
			total_fruits[cur_fruit] += 1
			if total_fruits[cur_fruit] == 1:
				unique_baskets += 1
			while unique_baskets >= 3:
				start_fruit = tree[start]
				total_fruits[start_fruit] -= 1
				if not total_fruits:
					unique_baskets -= 1
				start += 1
			max_fruit_types = max(max_fruit_types, end - start + 1)
		return max_fruit_types

class Solution:

	def totalFruit(self, tree):
		fruit_basket = collections.defaultdict(int)
		unique_fruits = 0
		total_fruits = 0
		start = 0
		end = 0
		for end in range(len(tree)):
			type_of_fruit = tree[end]
			fruit_basket[type_of_fruit] += 1
			if fruit_basket[type_of_fruit] == 1:
				unique_fruits += 1
			while unique_fruits > 2:
				start_fruit = tree[start]
				fruit_basket[start_fruit] -= 1
				if not fruit_basket[start_fruit]:
					unique_fruits -= 1
				start += 1
			total_fruits = max(total_fruits, end - start + 1)
		return total_fruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(ans, j) = (0, 0)
		n = len(tree)
		dic = {}
		for i in range(n):
			dic[tree[i]] = i
			if len(dic) > 2:
				ans = max(ans, i - j)
				k = None
				for key in dic:
					if key != tree[i] and key != tree[i - 1]:
						k = key
						j = dic[key] + 1
				del dic[k]
		return max(ans, n - j)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(nTrees, ans) = (len(tree), 0)
		if len(set(tree)) <= 2:
			return nTrees
		(i, j) = (0, 1)
		while i < j and j < nTrees:
			if len(set(tree[i:j + 1])) <= 2:
				j += 1
				ans = max(ans, j - i)
			else:
				i += 1
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		count = collections.Counter()
		for (index, value) in enumerate(tree):
			count[value] += 1
			if len(count) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
		return len(tree) - i


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		left = 0
		n = len(tree)
		ans = 0
		basket = set()
		counter = collections.Counter()
		for (right, fruit) in enumerate(tree):
			basket.add(fruit)
			counter[fruit] += 1
			while len(basket) > 2:
				counter[tree[left]] -= 1
				if counter[tree[left]] == 0:
					basket.remove(tree[left])
				left += 1
			ans = max(ans, right - left + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = i = 0
		count = collections.Counter()
		for (j, x) in enumerate(tree):
			count[x] += 1
			while len(count) >= 3:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = i = 0
		count = Counter()
		for (j, t) in enumerate(tree):
			count[t] += 1
			while len(count) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		start = 0
		max = 0
		reset = 0
		baskets = {1: [None, 0], 2: [None, 0]}
		while start < len(tree) and start >= 0:
			if baskets[1][0] == None:
				baskets[1][0] = tree[start]
				baskets[1][1] += 1
				while reset and start > 0:
					if baskets[1][0] != tree[start - 1]:
						reset = 0
					else:
						start -= 1
			elif baskets[1][0] == tree[start]:
				baskets[1][1] += 1
			elif baskets[2][0] == None:
				baskets[2][0] = tree[start]
				baskets[2][1] += 1
			elif baskets[2][0] == tree[start]:
				baskets[2][1] += 1
			else:
				if max < baskets[1][1] + baskets[2][1]:
					print((baskets, start))
				baskets = {1: [None, 0], 2: [None, 0]}
				reset = 1
			if reset == 1:
				if start > 0:
					start -= 1
			else:
				start += 1
			if max < baskets[1][1] + baskets[2][1]:
				max = baskets[1][1] + baskets[2][1]
		return max


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		finalMax = currentMax = last = secondLast = lastCount = 0
		for fruit in tree:
			if fruit == last or fruit == secondLast:
				currentMax += 1
			else:
				currentMax = lastCount + 1
			if fruit == last:
				lastCount += 1
			else:
				secondLast = last
				last = fruit
				lastCount = 1
			finalMax = max(finalMax, currentMax)
		return finalMax


from collections import Counter

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_fruits = 0
		window_start = 0
		freq = Counter()
		for (i, val) in enumerate(tree):
			freq[val] += 1
			while len(freq) > 2:
				to_delete = tree[window_start]
				freq[to_delete] -= 1
				if not freq[to_delete]:
					del freq[to_delete]
				window_start += 1
			max_fruits = max(max_fruits, i - window_start + 1)
		return max_fruits


class Solution:

	def totalFruit(self, trees: List[int]) -> int:
		if len(trees) <= 2:
			return len(trees)
		lp = 0
		rp = 1
		maxSize = 0
		hash = collections.defaultdict(int)
		lpInc = False
		rpInc = False
		curSet = set()
		hash[trees[lp]] += 1
		curSet.add(trees[lp])
		hash[trees[rp]] += 1
		curSet.add(trees[rp])
		while rp < len(trees):
			if lpInc:
				hash[trees[lp - 1]] = max(hash[trees[lp - 1]] - 1, 0)
				if hash[trees[lp - 1]] > 0:
					curSet.add(trees[lp - 1])
				else:
					curSet.remove(trees[lp - 1])
			if rpInc:
				hash[trees[rp]] += 1
				curSet.add(trees[rp])
			lpInc = False
			rpInc = False
			if len(curSet) <= 2:
				if rp - lp + 1 > maxSize:
					maxSize = rp - lp + 1
			if len(curSet) > 2:
				lp += 1
				lpInc = True
			else:
				rp += 1
				rpInc = True
		return maxSize


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		j = 0
		hm = {}
		maxL = 0
		while j < len(tree):
			if tree[j] in hm:
				hm[tree[j]] += 1
			elif len(hm) < 2:
				hm[tree[j]] = 1
			else:
				maxL = max(maxL, j - i)
				while i < j and len(hm) > 1:
					hm[tree[i]] -= 1
					if hm[tree[i]] == 0:
						del hm[tree[i]]
					i += 1
				hm[tree[j]] = 1
			j += 1
		maxL = max(maxL, j - i)
		return maxL


from collections import Counter

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		baskets = Counter()
		max_fr = 0
		i = 0
		for (j, t) in enumerate(tree):
			baskets[t] += 1
			while len(baskets) > 2:
				baskets[tree[i]] -= 1
				if baskets[tree[i]] == 0:
					del baskets[tree[i]]
				i += 1
			max_fr = max(max_fr, j - i + 1)
		return max_fr


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		fruitCap = [0] * len(tree)
		fruitCap[-1] = 1
		fruitA = tree[-1]
		fruitB = None
		for i in reversed(list(range(len(tree) - 1))):
			if tree[i] == fruitA or tree[i] == fruitB:
				fruitCap[i] = fruitCap[i + 1] + 1
			elif fruitB == None:
				fruitCap[i] = fruitCap[i + 1] + 1
				fruitB = tree[i]
			else:
				fruitA = tree[i]
				fruitB = tree[i + 1]
				fruitCap[i] = getConsecutive(tree, i + 1) + 1
		print(fruitCap)
		return max(fruitCap)

def getConsecutive(tree, index):
	consecutive = 0
	fruit = tree[index]
	for i in range(index, len(tree)):
		if tree[i] == fruit:
			consecutive += 1
		else:
			break
	return consecutive


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_fruits = 0
		counter = 0
		fruit_basket = set()
		i = 0
		while i < len(tree):
			if len(fruit_basket) < 2:
				counter += 1
				fruit_basket.add(tree[i])
				if len(fruit_basket) == 2:
					new_fruit_idx = i
			elif tree[i] in fruit_basket:
				counter += 1
			else:
				fruit_basket = set()
				max_fruits = max(counter, max_fruits)
				counter = 0
				i = new_fruit_idx - 1
			i += 1
		max_fruits = max(counter, max_fruits)
		return max_fruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_ = 0
		baskets = {}

		def get_other_tree(this_tree):
			trees = list(baskets.keys())
			return trees[1 - trees.index(this_tree)] if len(trees) == 2 else trees[0]
		for (idx, tr) in enumerate(tree):
			need_to_empty_1_basket = tr not in baskets and len(baskets) == 2
			if need_to_empty_1_basket:
				max_ = max(max_, sum((sum(baskets[b]) for b in baskets)))
				last_tree = tree[idx - 1]
				other_tree = get_other_tree(last_tree)
				baskets = {last_tree: [baskets[last_tree][1], 0], tr: [0, 1]}
			else:
				there_is_another_tree = tr not in baskets and len(baskets) == 1 or (tr in baskets and len(baskets) == 2)
				if there_is_another_tree:
					other_tree = get_other_tree(tr)
					baskets[other_tree] = [sum(baskets[other_tree]), 0]
				if tr not in baskets:
					baskets[tr] = [0, 0]
				baskets[tr][1] += 1
		return max(max_, sum((sum(baskets[b]) for b in baskets)))


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree or len(tree) == 0:
			return 0
		max_ = 1
		mem = {}
		(i, j) = (0, 0)
		while j < len(tree):
			if len(mem) <= 2:
				mem[tree[j]] = j
				j += 1
			if len(mem) > 2:
				min_ = len(tree) - 1
				for value in mem.values():
					min_ = min(min_, value)
				i = min_ + 1
				del mem[tree[min_]]
			max_ = max(max_, j - i)
		return max_


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		pre = -1
		ans = a = b = 0
		x = y = -1
		for cur in tree:
			if cur != x and cur != y:
				(x, y) = (pre, cur)
				(a, b) = (b, 1)
			elif cur == pre:
				b += 1
			else:
				a += b
				b = 1
			if a + b > ans:
				ans = a + b
			pre = cur
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		answer = 0
		currTree = 0
		numsDictionary = collections.Counter()
		for (treeIndex, fruit) in enumerate(tree):
			numsDictionary[fruit] += 1
			while len(numsDictionary) >= 3:
				numsDictionary[tree[currTree]] -= 1
				if numsDictionary[tree[currTree]] == 0:
					del numsDictionary[tree[currTree]]
				currTree += 1
			answer = max(answer, treeIndex - currTree + 1)
		return answer


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		counter = {}
		res = 0
		for (j, v) in enumerate(tree):
			counter[v] = counter.get(v, 0) + 1
			while len(counter) > 2:
				counter[tree[i]] -= 1
				if not counter[tree[i]]:
					del counter[tree[i]]
				i += 1
			res = max(res, j - i + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		next_start_pos = None
		max_len = 0
		s = set()
		res = []
		while i < len(tree):
			if tree[i] in s:
				max_len += 1
				i += 1
			elif len(s) == 0:
				s.add(tree[i])
				max_len += 1
				i += 1
			elif len(s) == 1:
				s.add(tree[i])
				max_len += 1
				next_start_pos = i
				i += 1
			elif len(s) == 2:
				res.append(max_len)
				max_len = 0
				s = set()
				i = next_start_pos
		res.append(max_len)
		return max(res)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(left, right) = (-1, 0)
		seen = Counter()
		ans = 0
		while left <= right < len(tree):
			while right < len(tree) and (len(seen) < 2 or tree[right] in seen):
				seen[tree[right]] += 1
				right += 1
			ans = max(ans, right - left - 1)
			left += 1
			seen[tree[left]] -= 1
			if seen[tree[left]] == 0:
				del seen[tree[left]]
		return ans


class Solution(object):

	def totalFruit(self, nums):
		d = {}
		k = 2
		maxL = 0
		L = 0
		for R in range(len(nums)):
			if nums[R] in d:
				d[nums[R]] += 1
			else:
				d[nums[R]] = 1
			while len(d) > k:
				d[nums[L]] -= 1
				if d[nums[L]] == 0:
					del d[nums[L]]
				L += 1
			maxL = max(maxL, R - L + 1)
		return maxL


class Track(object):

	def __init__(self, n=2):
		self.count = {}
		self.last = {}
		self.order = [None for _ in range(n - 1)]

	def is_new_elem(self, elem):
		return elem not in self.count

	def is_last_elem(self, elem):
		return elem in self.last

	def add(self, elem):
		if self.is_new_elem(elem):
			self.count = {elem: 1}
			for (key, val) in self.last.items():
				self.count[key] = val
		else:
			self.count[elem] += 1
		if self.is_last_elem(elem):
			self.last[elem] += 1
		else:
			if elem in self.order:
				del self.order[self.order.index(elem)]
			else:
				rem = self.order.pop(0)
				if rem is not None:
					del self.last[rem]
			self.last[elem] = 1
			self.order.append(elem)

	def get_count(self):
		total = 0
		for (_, val) in self.count.items():
			total += val
		return total

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		tracker = Track()
		max_count = 0
		for t in tree:
			tracker.add(t)
			max_count = max(max_count, tracker.get_count())
		return max_count


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = i = 0
		basket = {}
		for (j, x) in enumerate(tree):
			if x in basket:
				basket[x] += 1
			else:
				basket[x] = 1
			while len(basket) >= 3:
				basket[tree[i]] -= 1
				if basket[tree[i]] == 0:
					del basket[tree[i]]
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree) -> int:
		unit_first = tree[0]
		unit_second = -1
		amount_first = 0
		amount_second = 0
		max_amount = 0
		prev = tree[0]
		prev_amount = 0
		for i in range(len(tree)):
			if tree[i] == prev:
				prev_amount += 1
			if tree[i] == unit_first:
				amount_first += 1
			elif tree[i] == unit_second:
				amount_second += 1
			else:
				max_amount = max(max_amount, amount_first + amount_second)
				unit_first = prev
				amount_first = prev_amount
				unit_second = tree[i]
				amount_second = 1
			if tree[i] != prev:
				prev_amount = 1
			prev = tree[i]
		return max(max_amount, amount_first + amount_second)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(b1, b2, b1N, b2N, b2NCons, maxPick) = (None, None, 0, 0, 0, 0)
		for fruit in tree:
			if fruit == b2:
				(b2N, b2NCons) = (b2N + 1, b2NCons + 1)
			elif fruit == b1:
				(b1, b2, b1N, b2N, b2NCons) = (b2, b1, b2N, b1N + 1, 1)
			else:
				(b1, b2, b1N, b2N, b2NCons) = (b2, fruit, b2NCons, 1, 1)
			maxPick = max(maxPick, b1N + b2N)
		return maxPick


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = 0
		p = 0
		while p < len(tree):
			acc = 1
			first = tree[p]
			next_p = len(tree)
			second = -1
			for i in range(p + 1, len(tree)):
				if tree[i] != first:
					if second == -1:
						second = tree[i]
						next_p = i
					elif tree[i] != second:
						break
				acc += 1
				if i == len(tree) - 1:
					return max(ans, acc)
			p = next_p
			ans = max(ans, acc)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		type_cnt = {}
		max_fruit = -1
		left_ptr = 0
		last_cnt = 0
		while left_ptr < len(tree):
			right_ptr = left_ptr
			while right_ptr < len(tree) - 1 and tree[right_ptr] == tree[right_ptr + 1]:
				right_ptr += 1
			curr_type = tree[left_ptr]
			curr_cnt = right_ptr - left_ptr + 1
			if curr_type not in type_cnt:
				type_cnt[curr_type] = curr_cnt
			else:
				type_cnt[curr_type] += curr_cnt
			if len(type_cnt) > 2:
				type_cnt = {last_type: last_cnt, curr_type: curr_cnt}
			max_fruit = max(max_fruit, sum([cnt for cnt in list(type_cnt.values())]))
			last_cnt = curr_cnt
			last_type = curr_type
			left_ptr = right_ptr + 1
		return max_fruit


from collections import Counter

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		num_fruit = Counter()
		(j, num_type, max_fruit) = (0, 0, 0)
		for i in range(len(tree)):
			if num_fruit[tree[i]] == 0:
				num_type += 1
			num_fruit[tree[i]] += 1
			if num_type <= 2:
				max_fruit = max(i - j + 1, max_fruit)
			else:
				while True:
					num_fruit[tree[j]] -= 1
					j += 1
					if num_fruit[tree[j - 1]] == 0:
						break
				num_type -= 1
		return max_fruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		result = 0
		collected = {}
		i = 0
		for (j, fruit) in enumerate(tree):
			collected[fruit] = collected.get(fruit, 0) + 1
			while len(collected) > 2:
				collected[tree[i]] -= 1
				if not collected[tree[i]]:
					collected.pop(tree[i])
				i += 1
			result = max(result, j - i + 1)
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = i = 0
		freq = collections.defaultdict(int)
		for (j, fruit) in enumerate(tree):
			freq[fruit] += 1
			while len(freq) == 3:
				freq[tree[i]] -= 1
				if freq[tree[i]] == 0:
					del freq[tree[i]]
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) < 2:
			return len(tree)
		(start, end, res) = (0, 1, 1)
		basket = {tree[start]: 1}
		while end < len(tree):
			if tree[end] in basket:
				basket[tree[end]] += 1
				end += 1
				res = max(res, end - start)
			elif len(basket) < 2:
				basket[tree[end]] = 1
				end += 1
				res = max(res, end - start)
			else:
				basket[tree[start]] -= 1
				if basket[tree[start]] == 0:
					del basket[tree[start]]
				start += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 1:
			return 1
		l = 0
		r = 1
		curr_window = defaultdict(int)
		curr_window[tree[l]] += 1
		res = 1
		while r < len(tree):
			curr_window[tree[r]] += 1
			while len(curr_window) > 2:
				curr_window[tree[l]] -= 1
				if curr_window[tree[l]] == 0:
					del curr_window[tree[l]]
				l += 1
			if r - l + 1 > res:
				res = r - l + 1
			r += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		last_fruit = -1
		second_last_fruit = -1
		last_fruit_count = 0
		current_max = 0
		maxi = 0
		for fruit in tree:
			if fruit == last_fruit or fruit == second_last_fruit:
				current_max += 1
			else:
				current_max = last_fruit_count + 1
			if fruit == last_fruit:
				last_fruit_count += 1
			else:
				last_fruit_count = 1
			if fruit != last_fruit:
				second_last_fruit = last_fruit
				last_fruit = fruit
			maxi = max(current_max, maxi)
		return maxi


from collections import Counter

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = l = 0
		count = Counter()
		for (r, t) in enumerate(tree):
			count[t] += 1
			while len(count) >= 3:
				count[tree[l]] -= 1
				if count[tree[l]] == 0:
					del count[tree[l]]
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_length = 0
		fruits_frequency = defaultdict(int)
		window_start = 0
		for window_end in range(0, len(tree)):
			right_fruit = tree[window_end]
			fruits_frequency[right_fruit] += 1
			while len(fruits_frequency) > 2:
				left_fruit = tree[window_start]
				fruits_frequency[left_fruit] -= 1
				if fruits_frequency[left_fruit] == 0:
					del fruits_frequency[left_fruit]
				window_start += 1
			max_length = max(max_length, window_end - window_start + 1)
		return max_length


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		count2 = 0
		basket = 0
		ans = 0
		(kind1, kind2) = (0, 0)
		for t in tree:
			if t == kind2:
				count2 += 1
				basket += 1
			elif t == kind1:
				count2 = 1
				basket += 1
				(kind1, kind2) = (kind2, kind1)
			else:
				basket = count2 + 1
				count2 = 1
				(kind1, kind2) = (kind2, t)
			ans = max(ans, basket)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		left = ans = 0
		types = collections.defaultdict(int)
		for right in range(len(tree)):
			types[tree[right]] += 1
			if len(types.keys()) <= 2:
				ans = max(ans, right - left + 1)
			while len(types.keys()) > 2:
				types[tree[left]] -= 1
				if types[tree[left]] == 0:
					types.pop(tree[left])
				left += 1
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(l, r, ans) = (0, 0, 0)
		counter = Counter()
		length = 0
		while r < len(tree):
			counter[tree[r]] += 1
			length = len(counter)
			r += 1
			while length > 2:
				counter[tree[l]] -= 1
				if counter[tree[l]] == 0:
					del counter[tree[l]]
					length -= 1
				l += 1
			ans = max(ans, r - l)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxStreak = 0
		i = 0
		types = set()
		last_type = 0
		streak = 0
		while i < len(tree):
			if len(types) == 0 or len(types) == 1:
				types.add(tree[i])
				last_type = i
				streak += 1
				i += 1
			elif tree[i] in types:
				if tree[last_type] != tree[i]:
					last_type = i
				streak += 1
				i += 1
			else:
				i = last_type
				types = set()
				maxStreak = max(streak, maxStreak)
				streak = 0
		return max(streak, maxStreak)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		cnt = 1
		max = 1
		keys = set([tree[0]])
		spree = [tree[0], 1]
		for k in range(1, len(tree)):
			if tree[k] in keys:
				cnt += 1
				if tree[k] == spree[0]:
					spree[1] += 1
				else:
					spree = [tree[k], 1]
			elif len(keys) == 1:
				keys.add(tree[k])
				cnt += 1
				spree = [tree[k], 1]
			else:
				if cnt > max:
					max = cnt
				keys = set([tree[k - 1], tree[k]])
				cnt = spree[1] + 1
				spree = [tree[k], 1]
		if cnt > max:
			max = cnt
		return max


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		start = 0
		end = 1
		maxLength = 1
		types = {}
		types[tree[0]] = 1
		if len(tree) <= 2:
			return len(tree)
		while end < len(tree) - 1 or start < end:
			if end < len(tree) - 1 and len(types) < 2:
				if types.get(tree[end]):
					types[tree[end]] += 1
				else:
					types[tree[end]] = 1
				end += 1
			elif end == len(tree) or types.get(tree[end]) == None:
				types[tree[start]] -= 1
				if types[tree[start]] == 0:
					del types[tree[start]]
				start += 1
			else:
				if types.get(tree[end]):
					types[tree[end]] += 1
				else:
					types[tree[end]] = 1
				end += 1
			if len(types) <= 2:
				maxLength = max(maxLength, end - start)
		return maxLength


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) <= 1:
			return len(tree)
		if len(list(set(tree))) == 2:
			return len(tree)
		maxCount = 0
		classes = []
		i = 0
		while i < len(tree):
			j = i + 1
			classes = [tree[i]]
			count = 1
			secFruitStart = -1
			while len(classes) <= 2 and j < len(tree):
				if tree[j] not in classes:
					classes.append(tree[j])
					if len(classes) == 2:
						secFruitStart = j
				if len(classes) == 3:
					continue
				count = count + 1
				j = j + 1
			if count > maxCount:
				maxCount = count
			if secFruitStart != -1:
				i = secFruitStart
			else:
				break
		return maxCount


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		start = 0
		end = 0
		le = len(tree)
		hmap = collections.defaultdict(int)
		count = 0
		res = 0
		while end < le:
			hmap[tree[end]] += 1
			if hmap[tree[end]] == 1:
				count += 1
			end += 1
			while count > 2 and start < end:
				hmap[tree[start]] -= 1
				if hmap[tree[start]] == 0:
					count -= 1
				start += 1
			if count > 2:
				continue
			res = max(res, end - start)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		secondLastFruit = -1
		lastFruit = -1
		lastFruitCount = 0
		currFruits = 0
		maxFruits = 0
		for fruit in tree:
			if fruit == lastFruit or fruit == secondLastFruit:
				currFruits += 1
			else:
				currFruits = lastFruitCount + 1
			if fruit == lastFruit:
				lastFruitCount += 1
			else:
				lastFruitCount = 1
				secondLastFruit = lastFruit
				lastFruit = fruit
			maxFruits = max(currFruits, maxFruits)
		return maxFruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(i, maxLen) = (0, 0)
		cache = collections.defaultdict(int)
		for j in range(len(tree)):
			cache[tree[j]] += 1
			if len(cache) <= 2:
				maxLen = max(maxLen, j - i + 1)
			while len(cache) > 2:
				cache[tree[i]] -= 1
				if cache[tree[i]] == 0:
					del cache[tree[i]]
				i += 1
		if maxLen == 0:
			return 1
		return maxLen


class Solution:

	def totalFruit(self, tree) -> int:
		n = len(tree)
		if n <= 2:
			return n
		tem = collections.Counter()
		res = 0
		i = 0
		j = 1
		tem.update(tree[:1])
		while j < n:
			while j < n and len(tem.keys()) <= 2:
				tem.update([tree[j]])
				res = max(res, j - i)
				j += 1
			while len(tem.keys()) >= 3:
				tem[tree[i]] -= 1
				if tem[tree[i]] == 0:
					tem.pop(tree[i])
				i += 1
			if j == n:
				res = max(res, j - i)
				break
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = 0
		mres = 0
		temp = set()
		i = 0
		newidx = 0
		while i < len(tree):
			if len(temp) == 0:
				mres += 1
				temp.add(tree[i])
				i += 1
			elif len(temp) == 1:
				newidx = i
				temp.add(tree[i])
				mres += 1
				i += 1
			elif tree[i] in temp:
				mres += 1
				i += 1
			else:
				res = max(res, mres)
				mres = 0
				temp = set()
				i = newidx
		res = max(res, mres)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		if len(set(tree)) <= 2:
			return len(tree)
		max_collected = 0
		for i in range(len(tree)):
			num_collected = 0
			different_types = set()
			for j in range(i, len(tree)):
				if len(different_types) < 2:
					different_types.add(tree[j])
					num_collected += 1
				elif tree[j] in different_types:
					num_collected += 1
				else:
					break
			max_collected = max(max_collected, num_collected)
		return max_collected


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		item1_val = -1
		item1_fs = -1
		item1_ls = -1
		item2_val = -1
		item2_fs = -1
		item2_ls = -1
		size = list()
		for i in range(len(tree)):
			if tree[i] == item1_val:
				item1_ls = i
				if item1_fs == -1:
					item1_ls = i
				if i == 0:
					size.append(1)
				size.append(size[i - 1] + 1)
			elif tree[i] == item2_val:
				item2_ls = i
				if item2_fs == -1:
					item2_ls = i
				if i == 0:
					size.append(1)
				size.append(size[i - 1] + 1)
			elif item1_ls > item2_ls:
				item1_fs = item2_ls + 1
				item2_val = tree[i]
				item2_fs = i
				item2_ls = i
				size.append(i - item1_fs + 1)
			else:
				item2_fs = item1_ls + 1
				item1_val = tree[i]
				item1_fs = i
				item1_ls = i
				size.append(i - item2_fs + 1)
		return max(size)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		counter = collections.defaultdict(int)
		start = 0
		res = 0
		for end in range(len(tree)):
			counter[tree[end]] += 1
			while len(list(counter.keys())) > 2:
				counter[tree[start]] -= 1
				if counter[tree[start]] == 0:
					del counter[tree[start]]
				start += 1
			res = max(res, sum(counter.values()))
		return res


from collections import defaultdict

class Solution:

	def totalFruit(self, tree):
		if len(tree) < 3:
			return len(tree)
		best_pair = 0
		forest = defaultdict(int)
		forest[tree[0]] = (0, 1)
		for t in range(1, len(tree)):
			if tree[t] not in forest:
				best_pair = max([best_pair, sum([b for basket in list(forest.values()) for b in basket])])
				temp = defaultdict(int)
				temp[tree[t]] = (0, 0)
				temp[tree[t - 1]] = (0, forest[tree[t - 1]][-1])
				forest = temp
			if tree[t] == tree[t - 1]:
				forest[tree[t]] = (forest[tree[t]][0], forest[tree[t]][-1] + 1)
			else:
				forest[tree[t]] = (sum(forest[tree[t]]), 1)
		best_pair = max([best_pair, sum([b for basket in list(forest.values()) for b in basket])])
		return best_pair


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		c = collections.Counter()
		j = 0
		ans = 0
		for i in range(len(tree)):
			c[tree[i]] += 1
			while len(c) >= 3:
				c[tree[j]] -= 1
				if c[tree[j]] == 0:
					del c[tree[j]]
				j += 1
			ans = max(ans, i - j + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		prev_count = curr = count_b = result = 0
		a = None
		b = None
		for c in tree:
			if b == c:
				curr += 1
				count_b += 1
			elif a == c:
				curr += 1
				count_b = 1
				a = b
				b = c
			elif a != c and b != c:
				curr = count_b + 1
				count_b = 1
				a = b
				b = c
			result = max(result, curr)
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		current_picking = tree[0]
		prev_picking = None
		max_picked = 0
		baskets = {current_picking: [0, 0]}
		for i in range(len(tree)):
			if tree[i] != current_picking:
				if len(baskets) < 2:
					baskets[current_picking] = [0, i - 1]
					prev_picking = current_picking
					current_picking = tree[i]
					baskets[current_picking] = [i, i]
				elif tree[i] != prev_picking:
					baskets = {current_picking: [baskets[prev_picking][1] + 1, baskets[current_picking][1]], tree[i]: [i, i]}
					prev_picking = current_picking
					current_picking = tree[i]
				else:
					(prev_picking, current_picking) = (current_picking, prev_picking)
					baskets[current_picking][1] = i
			else:
				baskets[current_picking][1] = i
			if baskets.get(current_picking) and baskets.get(prev_picking):
				max_picked = max(max_picked, max([pos[1] for pos in baskets.values()]) - min([pos[0] for pos in baskets.values()]) + 1)
			else:
				max_picked = max(max_picked, baskets[current_picking][1] - baskets[current_picking][0] + 1)
		return max_picked


from collections import Counter

class window:

	def __init__(self):
		self.type = Counter()

	def add(self, x):
		self.type[x] += 1

	def remove(self, x):
		self.type[x] -= 1
		if self.type[x] == 0:
			del self.type[x]

	def valid(self):
		return len(self.type) <= 2

class Solution:

	def totalFruit(self, tree):
		win = window()
		(l, res) = (0, 0)
		for (r, fruit) in enumerate(tree):
			win.add(fruit)
			while l < r and (not win.valid()):
				win.remove(tree[l])
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		n = len(tree)
		res = 1
		last_occur = {tree[0]: 0}
		(i, j) = (0, 1)
		while j < n:
			new_type = tree[j]
			if new_type in last_occur or len(last_occur.keys()) < 2:
				last_occur[new_type] = j
				res = max(res, j - i + 1)
			else:
				count = j - i
				res = max(res, count)
				keys = list(last_occur.keys())
				t = keys[0] if last_occur[keys[0]] < last_occur[keys[1]] else keys[1]
				i = last_occur[t] + 1
				del last_occur[t]
				last_occur[new_type] = j
			j += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxL = 0
		(l, r) = (0, 0)
		if len(set(tree)) < 3:
			return len(tree)
		while r <= len(tree):
			temp = tree[l:r]
			if len(set(temp)) < 3:
				maxL = max(maxL, len(temp))
				r += 1
			elif len(set(temp)) >= 3:
				l += 1
		return maxL


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		firstFruit = secondFruit = -1
		firstQuant = secondQuant = 0
		ans = 0
		n = len(tree)
		i = 0
		while i < n:
			if firstQuant == 0 or firstFruit == tree[i]:
				firstFruit = tree[i]
				firstQuant += 1
			elif secondQuant == 0 or secondFruit == tree[i]:
				secondFruit = tree[i]
				secondQuant += 1
			elif i > 0 and tree[i - 1] == firstFruit:
				secondFruit = tree[i]
				secondQuant = 1
				j = i - 1
				while j >= 0 and tree[j] == firstFruit:
					j -= 1
				firstQuant = i - 1 - j
			elif i > 0 and tree[i - 1] == secondFruit:
				firstFruit = tree[i]
				firstQuant = 1
				j = i - 1
				while j >= 0 and tree[j] == secondFruit:
					j -= 1
				secondQuant = i - 1 - j
			ans = max(ans, firstQuant + secondQuant)
			i += 1
		return ans


class Solution:

	def totalFruit(self, ar: List[int]) -> int:
		l = list(set(ar))
		if len(l) <= 2:
			return len(ar)
		else:
			m = 0
			for i in range(0, len(ar)):
				l = [ar[i]]
				d = 1
				for j in range(i + 1, len(ar)):
					if ar[j] in l:
						l.append(ar[j])
					elif ar[j] not in l and d == 1:
						d += 1
						l.append(ar[j])
					else:
						break
				m = max(m, len(l))
			return m


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 1:
			return 1
		window_start = 0
		window_end = 2
		total_max = 2
		if tree[0] == tree[1]:
			tmp_index = 0
		else:
			tmp_index = 1
		fruit_type = set(tree[:2])
		for i in range(2, len(tree)):
			if tree[i] in fruit_type or len(fruit_type) < 2:
				window_end += 1
				if tree[i] != tree[i - 1]:
					tmp_index = i
				fruit_type.add(tree[i])
			else:
				window_start = tmp_index
				tmp_index = i
				window_end += 1
				fruit_type = set(tree[i - 1:i + 1])
			if window_end - window_start > total_max:
				total_max = window_end - window_start
		return total_max


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		dp = [[] for i in range(len(tree))]
		dp[-1] = [1, 1, [tree[-1]]]
		res = 1
		for i in reversed(list(range(len(tree) - 1))):
			if tree[i] == tree[i + 1]:
				dp[i] = [dp[i + 1][0] + 1, dp[i + 1][1] + 1, dp[i + 1][2]]
			elif len(dp[i + 1][2]) == 1:
				dp[i] = [dp[i + 1][0] + 1, 1, [tree[i], dp[i + 1][2][0]]]
			elif tree[i] in dp[i + 1][2]:
				dp[i] = [dp[i + 1][0] + 1, 1, dp[i + 1][2]]
			else:
				dp[i] = [1 + dp[i + 1][1], 1, [tree[i], tree[i + 1]]]
			res = max(res, dp[i][0])
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		N = len(tree)
		out = 0
		start = 0
		olderstart = 0
		newerend = newerstart = 0
		olderend = olderstart = 0
		older = newer = tree[0]
		j = 0
		if N < 3:
			return len(tree)
		while newer == older and j < N:
			olderend = j
			j += 1
			if j == N:
				return N
			newer = tree[j]
			newerstart = j
		assert newer != older
		for i in range(j, N):
			curr = tree[i]
			if curr == older or curr == newer:
				if curr == older:
					olderend = i
				if curr == newer:
					newerend = i
			else:
				if prev == older:
					olderstart = newerend + 1
				else:
					olderstart = olderend + 1
					olderend = newerend
					older = newer
				newerstart = i
				newerend = i
				newer = curr
			prev = curr
			out = max(i - olderstart + 1, out)
		return out


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) <= 2:
			return len(tree)
		n = len(tree)
		res = 0
		start = 0
		while start < n:
			(type1, type2, type2_pos) = (-1, -1, -1)
			i = start
			while i < n:
				if type1 == -1:
					type1 = tree[i]
				elif tree[i] != type1 and type2 == -1:
					type2 = tree[i]
					type2_pos = i
				elif tree[i] != type1 and tree[i] != type2:
					break
				i += 1
			res = max(res, i - start)
			if i == n:
				break
			start = type2_pos
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		total_len = len(tree)
		if total_len == 0:
			return 0
		rst = 1
		fruit_1 = tree[0]
		start = 0
		while tree[start] == fruit_1:
			start += 1
			if start >= total_len:
				return start
		fruits = [fruit_1, tree[start]]
		fruits_order = [start - 1, start]
		total_fruits = start + 1
		for i in range(start + 1, total_len):
			if tree[i] == fruits[0]:
				fruits_order[0] = i
				total_fruits += 1
			elif tree[i] == fruits[1]:
				fruits_order[1] = i
				total_fruits += 1
			else:
				if total_fruits > rst:
					rst = total_fruits
				if fruits_order[0] > fruits_order[1]:
					fruits[1] = tree[i]
					total_fruits = i - fruits_order[1]
					fruits_order[1] = i
				else:
					fruits[0] = tree[i]
					total_fruits = i - fruits_order[0]
					fruits_order[0] = i
		if total_fruits > rst:
			return total_fruits
		return rst


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		out = 0
		for i in range(len(tree)):
			tot = self.getTotalAtIndex(tree, i)
			if tot > out:
				out = tot
			if tot == len(tree):
				break
		return out

	def getTotalAtIndex(self, tree, i):
		fruit_types = set()
		cnt = 0
		for j in range(i, len(tree)):
			if len(fruit_types) < 2:
				fruit_types.add(tree[j])
			if tree[j] in fruit_types:
				cnt += 1
			else:
				break
		return cnt
		pass


from collections import defaultdict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		st = 0
		max_len = 0
		basket = defaultdict(int)
		for end in range(len(tree)):
			basket[tree[end]] += 1
			while len(basket) > 2:
				basket[tree[st]] -= 1
				if basket[tree[st]] == 0:
					del basket[tree[st]]
				st += 1
			total = 0
			for k in basket:
				total += basket[k]
			max_len = max(max_len, total)
		return max_len


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		n = len(tree)
		if n < 3:
			return n
		max_count = 0
		dp = [[set(), 0, set(), 0] for _ in range(n)]
		dp[0] = [{tree[0]}, 1, {tree[0]}, 1]
		for i in range(1, n):
			if tree[i] in dp[i - 1][2]:
				set_2 = dp[i - 1][2].copy()
				count_2 = dp[i - 1][3] + 1
			else:
				temp = dp[i - 1][0].copy()
				temp.add(tree[i])
				set_2 = temp
				count_2 = dp[i - 1][1] + 1
			if tree[i] in dp[i - 1][0]:
				set_1 = dp[i - 1][0].copy()
				count_1 = dp[i - 1][1] + 1
			else:
				set_1 = {tree[i]}
				count_1 = 1
			dp[i] = [set_1, count_1, set_2, count_2]
			max_count = max(max_count, max(count_1, count_2))
		return max_count


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		count = collections.Counter()
		i = ans = 0
		for j in range(len(tree)):
			fruit = tree[j]
			count[fruit] += 1
			while len(count.keys()) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) <= 2:
			return len(tree)
		types = {tree[0]: 0, tree[1]: 1} if tree[0] != tree[1] else {tree[0]: 1}
		res = 2
		temp = 2
		for i in range(2, len(tree)):
			if len(types) == 2:
				if tree[i] not in types:
					res = max(res, temp)
					delete = sorted(types, key=types.get)[0]
					temp = i - types[delete]
					del types[delete]
					types[tree[i]] = i
				else:
					temp += 1
					types[tree[i]] = i
			else:
				temp += 1
				types[tree[i]] = i
		res = max(res, temp)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(left_pointer, right_pointer) = (0, 0)
		fruits = 0
		fruits_in_basket = {}
		while right_pointer < len(tree):
			if len(fruits_in_basket) <= 2:
				fruits_in_basket[tree[right_pointer]] = right_pointer
				right_pointer += 1
			if len(fruits_in_basket) > 2:
				minimum_index = len(tree)
				for index in list(fruits_in_basket.values()):
					minimum_index = min(minimum_index, index)
				left_pointer = minimum_index + 1
				fruits_in_basket.pop(tree[minimum_index])
			fruits = max(fruits, right_pointer - left_pointer)
		return fruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if tree == [] or tree is None:
			return 0
		if len(tree) == 1:
			return 1
		s = 0
		max = 1
		count = max
		for i in range(len(tree)):
			j = i + 1
			b1 = tree[i]
			b2 = tree[j]
			count = 1
			if b1 == b2:
				while j < len(tree) and tree[j] == b1:
					j += 1
					count += 1
				if j != len(tree):
					b2 = tree[j]
				elif count > max:
					return count
			while j < len(tree):
				if tree[j] != b1 and tree[j] != b2:
					if count >= max:
						max = count
					break
				count += 1
				j += 1
				if j == len(tree):
					if count >= max:
						max = count
					return max
		return max


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		char_to_count = defaultdict(int)
		unique_chars = 0
		start = 0
		end = 0
		max_fruit = 0
		while end < len(tree):
			char_to_count[tree[end]] += 1
			if char_to_count[tree[end]] == 1:
				unique_chars += 1
			while unique_chars > 2:
				char_to_count[tree[start]] -= 1
				if char_to_count[tree[start]] == 0:
					unique_chars -= 1
				start += 1
			end += 1
			max_fruit = max(max_fruit, end - start)
		return max_fruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		d = {}
		first = -1
		second = -1
		i = 0
		n = len(tree)
		m = -1
		while i < n:
			if tree[i] in d:
				d[tree[i]].append(i)
				i += 1
			elif len(list(d.keys())) == 2:
				s = 0
				for (k, v) in list(d.items()):
					s += len(v)
				m = max(m, s)
				if d[first][-1] > d[second][-1]:
					i = d[second][-1] + 1
					first = first
					d = {}
					d[tree[i]] = [i]
					i += 1
				else:
					i = d[first][-1] + 1
					first = second
					d = {}
					d[tree[i]] = [i]
					i += 1
			elif len(list(d.keys())) == 1:
				second = tree[i]
				d[tree[i]] = [i]
				i += 1
			else:
				first = tree[i]
				d[tree[i]] = [i]
				i += 1
		s = 0
		for (k, v) in list(d.items()):
			s += len(v)
		return max(m, s)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		a = Counter(tree)
		if len(a) <= 2:
			return len(tree)
		ans = 0
		i = 0
		while i < len(tree):
			count = 1
			basket = [tree[i]]
			j = i + 1
			while j < len(tree):
				if tree[j] in basket:
					count += 1
				elif len(basket) >= 2:
					break
				else:
					basket.append(tree[j])
					count += 1
				j += 1
			if count > ans:
				ans = count
			i += 1
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(set(tree)) <= 2:
			return len(tree)
		types = set()
		maxFruits = 0
		for i in range(len(tree)):
			start = i
			res = 0
			types = set()
			for i in range(start, len(tree)):
				fruitType = tree[i]
				if len(types) >= 2 and fruitType not in types:
					break
				elif fruitType in types:
					res += 1
				else:
					types.add(fruitType)
					res += 1
			maxFruits = max(maxFruits, res)
		return maxFruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		dic = {}
		first = 0
		i = 0
		n = len(tree)
		ans = 0
		while i < n:
			val = tree[i]
			if val in dic:
				dic[val] += 1
			elif len(dic) < 2:
				dic[val] = 1
			else:
				dic[val] = 1
				while len(dic) >= 2:
					v2 = tree[first]
					first += 1
					dic[v2] -= 1
					if dic[v2] == 0:
						dic.pop(v2, None)
						break
			ans = max(i - first + 1, ans)
			i += 1
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		fruits = tree
		window_start = 0
		max_length = 0
		fruit_frequency = {}
		for window_end in range(len(fruits)):
			right_fruit = fruits[window_end]
			if right_fruit not in fruit_frequency:
				fruit_frequency[right_fruit] = 0
			fruit_frequency[right_fruit] += 1
			while len(fruit_frequency) > 2:
				left_fruit = fruits[window_start]
				fruit_frequency[left_fruit] -= 1
				if fruit_frequency[left_fruit] == 0:
					del fruit_frequency[left_fruit]
				window_start += 1
			max_length = max(max_length, window_end - window_start + 1)
		return max_length


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		best_attempt = 0
		for i in range(len(tree)):
			baskets = {}
			for j in range(i, len(tree)):
				if tree[j] in baskets:
					baskets[tree[j]] += 1
				elif len(baskets) >= 2:
					break
				else:
					baskets[tree[j]] = 1
			attempt_val = sum(baskets.values())
			if attempt_val > best_attempt:
				best_attempt = attempt_val
			if best_attempt > len(tree) - i:
				break
		return best_attempt


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = 0
		N = len(tree)
		oneidx = twoidx = 0
		onetype = tree[0]
		twotype = None
		(left, right) = (0, 0)
		while right < N and tree[right] == onetype:
			oneidx += 1
			right += 1
		oneidx -= 1
		if right == N:
			return N
		twotype = tree[right]
		twoidx = right
		while right < N:
			if tree[right] == onetype:
				oneidx = right
			elif tree[right] == twotype:
				twoidx = right
			else:
				res = max(res, right - left)
				if oneidx < twoidx:
					left = oneidx + 1
					onetype = tree[right]
					oneidx = right
				else:
					left = twoidx + 1
					twotype = tree[right]
					twoidx = right
			right += 1
		return max(res, right - left)


from collections import OrderedDict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		last_index_of = OrderedDict()
		ans = l = 0
		for (i, t) in enumerate(tree):
			last_index_of[t] = i
			last_index_of.move_to_end(t)
			if len(last_index_of) > 2:
				ans = max(ans, i - l)
				l = last_index_of.popitem(last=False)[1] + 1
		ans = max(ans, len(tree) - l)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(first, sec) = (0, 0)
		curr_hash = {}
		if len(tree) < 3:
			return len(tree)
		Max = [float('-inf')]
		while first < len(tree):
			first = self.first_pass(first, curr_hash, tree, Max)
			if first > len(tree):
				continue
			sec = self.sec_pass(sec, first, curr_hash, tree)
		return Max[0]

	def first_pass(self, pointer, hash, trees, Max):
		count = 0
		for key in hash:
			count += hash[key]
		while pointer < len(trees):
			typ = trees[pointer]
			if typ in hash:
				hash[typ] += 1
			elif len(hash) < 2:
				hash[typ] = 1
			else:
				break
			count += 1
			pointer += 1
		Max[0] = max(Max[0], count)
		return pointer

	def sec_pass(self, sec, first, hash, tree):
		while sec < first and len(hash) > 1:
			typ = tree[sec]
			if hash[typ] == 1:
				del hash[typ]
			else:
				hash[typ] -= 1
			sec += 1
		return sec


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		k = 2
		left = 0
		cnt = collections.Counter()
		res = 0
		for (j, i) in enumerate(tree):
			if cnt[i] == 0:
				k -= 1
			cnt[i] += 1
			while k < 0:
				cnt[tree[left]] -= 1
				if cnt[tree[left]] == 0:
					k += 1
				left += 1
			res = max(res, j - left + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		c = 0
		p = 0
		for i in range(len(tree)):
			l = []
			k = 0
			for j in range(i, len(tree)):
				if tree[j] not in l:
					l.append(tree[j])
					k += 1
				else:
					k += 1
				if len(l) > 2:
					k = k - 1
					break
			if k > p:
				p = k
			if p == len(tree):
				break
		return p


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_count = 0
		tree_len = len(tree)
		if len(tree) == 1:
			return 1
		if len(set(tree)) in (1, 2):
			return len(tree)
		for i in range(tree_len - 1):
			tree_set = set()
			tree_set.add(tree[i])
			count = 1
			for j in range(i + 1, tree_len):
				if tree[j] not in tree_set and len(tree_set) == 2:
					break
				tree_set.add(tree[j])
				count += 1
			max_count = max(max_count, count)
		return max_count


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		blocks = [(k, len(list(v))) for (k, v) in itertools.groupby(tree)]
		ans = i = 0
		while i < len(blocks):
			(types, weight) = (set(), 0)
			for j in range(i, len(blocks)):
				types.add(blocks[j][0])
				weight += blocks[j][1]
				if len(types) >= 3:
					i = j - 1
					break
				ans = max(ans, weight)
			else:
				break
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		st = c = res = 0
		dic = dict()
		for end in range(len(tree)):
			if tree[end] in dic:
				dic[tree[end]] += 1
			else:
				dic[tree[end]] = 1
				c += 1
			while c > 2:
				dic[tree[st]] -= 1
				if dic[tree[st]] == 0:
					del dic[tree[st]]
					c -= 1
				st += 1
			res = max(res, end - st + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		insp = {}
		pos = {}
		mxx = -1
		i = 0
		while i < len(tree):
			f = tree[i]
			if f not in insp and len(insp) == 2:
				mnn = math.inf
				tod = None
				for (of, op) in list(pos.items()):
					mnn = min(mnn, op)
					if mnn == op:
						tod = of
				k = pos[tod]
				while k >= 0:
					of = tree[k]
					if of not in pos:
						break
					insp[of] -= 1
					k -= 1
				del pos[tod]
				del insp[tod]
				insp[f] = 0
			elif f not in insp:
				insp[f] = 0
			pos[f] = i
			insp[f] += 1
			score = self.get_basketsize(insp)
			mxx = max(mxx, score)
			i += 1
		return mxx

	def get_basketsize(self, insp):
		mxx = 0
		nmxx = 0
		for (f, ct) in list(insp.items()):
			if ct >= mxx:
				nmxx = max(mxx, nmxx)
				mxx = max(ct, mxx)
			elif ct >= nmxx:
				nmxx = max(ct, nmxx)
		return mxx + nmxx


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		counter = collections.Counter()
		l = r = 0
		res = 0
		while r < len(tree):
			counter[tree[r]] += 1
			while len(counter.keys()) > 2:
				counter[tree[l]] -= 1
				if counter[tree[l]] == 0:
					del counter[tree[l]]
				l += 1
			res = max(res, sum(counter.values()))
			r += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		start = end = disFruits = curTotal = maxTotal = 0
		fruits = {}
		while end < len(tree):
			curFruit = tree[end]
			frontFruit = tree[start]
			if curFruit not in fruits and disFruits == 2:
				if fruits[frontFruit] == 1:
					del fruits[frontFruit]
					disFruits -= 1
				else:
					fruits[frontFruit] -= 1
				curTotal -= 1
				start += 1
			else:
				curFruit = tree[end]
				if curFruit not in fruits:
					fruits[curFruit] = 1
					disFruits += 1
				else:
					fruits[curFruit] += 1
				curTotal += 1
				maxTotal = max(curTotal, maxTotal)
				end += 1
		return maxTotal


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 1:
			return 1
		start = last1 = last2 = 0
		res = 1
		for i in range(1, len(tree)):
			if tree[i] == tree[last1]:
				last1 = i
			elif tree[i] == tree[last2]:
				last2 = i
			elif tree[last1] == tree[last2]:
				last1 = max(last1, last2)
				last2 = i
			else:
				start = min(last1, last2) + 1
				if last1 < last2:
					last1 = i
				else:
					last2 = i
			res = max(res, i - start + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:

		def pick(start, end):
			res = 0
			fruitType = set()
			for i in range(start, end):
				fruit = tree[i]
				if fruit not in fruitType and len(fruitType) >= 2:
					return res
				fruitType.add(fruit)
				res += 1
			return res
		n = len(tree)
		cnt = Counter(tree)
		if len(cnt) <= 2:
			return n
		maxFruit = 0
		for i in range(n):
			maxFruit = max(maxFruit, pick(i, n))
		return maxFruit


from collections import defaultdict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		counter = {}
		longest = 0
		fruits = 0
		i = 0
		for j in range(len(tree)):
			if tree[j] not in counter:
				fruits += 1
				counter[tree[j]] = 0
			counter[tree[j]] += 1
			while fruits > 2:
				counter[tree[i]] -= 1
				if counter[tree[i]] == 0:
					fruits -= 1
					del counter[tree[i]]
				i += 1
			longest = max(longest, j - i + 1)
		return longest


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 1:
			return 1
		if not tree:
			return 0
		i = 0
		j = 1
		l = len(tree)
		ans = 0
		found = False
		second = tree[1]
		count = 1
		while i < l and j < l:
			if tree[i] != tree[j] and (not found):
				second = tree[j]
				found = True
			if found and tree[j] != second and (tree[j] != tree[i]):
				ans = max(ans, count)
				count = 0
				i += 1
				j = i
				found = False
			j += 1
			count += 1
		ans = max(ans, count)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		fruit_dict = collections.defaultdict(int)
		(j, result, count) = (0, 0, 0)
		for (i, t) in enumerate(tree):
			fruit_dict[t] += 1
			count += 1
			while len(fruit_dict) > 2 and j < len(tree):
				fruit_dict[tree[j]] -= 1
				count -= 1
				if fruit_dict[tree[j]] == 0:
					del fruit_dict[tree[j]]
				j += 1
			if len(fruit_dict) <= 2:
				result = max(result, count)
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		blocks = [(k, len(list(v))) for (k, v) in itertools.groupby(tree)]
		(i, result) = (0, 0)
		while i < len(blocks):
			j = i
			count = 0
			fruit_set = set()
			while j < len(blocks):
				fruit_set.add(blocks[j][0])
				count += blocks[j][1]
				if len(fruit_set) > 2:
					i = j - 1
					break
				result = max(result, count)
				j += 1
			else:
				break
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		count = collections.Counter()
		j = res = 0
		for i in range(len(tree)):
			count[tree[i]] += 1
			while len(count) > 2:
				count[tree[j]] -= 1
				if count[tree[j]] == 0:
					del count[tree[j]]
				j += 1
			res = max(res, sum(count.values()))
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = []
		ind = 0
		if len(tree) == 1:
			return 1
		if len(set(tree)) <= 2:
			return len(tree)
		while ind < len(tree) - 1:
			count = 0
			types = set()
			for i in range(ind, len(tree)):
				types.add(tree[i])
				if len(types) > 2:
					break
				count += 1
			res.append(count)
			ind += 1
		return max(res)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		grp = []
		(x, y) = (tree[0], 1)
		for e in tree[1:]:
			if e == x:
				y += 1
			else:
				grp.append((x, y))
				(x, y) = (e, 1)
		grp.append((x, y))
		ret = 0
		(pair, pair_sum) = ([], 0)
		for i in range(len(grp)):
			(x, y) = grp[i]
			if x in pair:
				pair_sum += y
			elif len(pair) < 2:
				pair = pair + [x]
				pair_sum += y
			else:
				pair = [grp[i - 1][0]] + [x]
				pair_sum = grp[i - 1][1] + y
			ret = max(ret, pair_sum)
		return ret


from collections import defaultdict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		(freq, ftypes, ans, i) = (defaultdict(int), set(), float('-inf'), 0)
		for (j, num) in enumerate(tree):
			freq[num] += 1
			ftypes.add(num)
			while len(ftypes) > 2:
				freq[tree[i]] -= 1
				if freq[tree[i]] == 0:
					ftypes.remove(tree[i])
				i += 1
			ans = max(ans, j - i + 1)
			j += 1
		return ans


import collections

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		res = i = 0
		count = Counter()
		for (j, k) in enumerate(tree):
			count[tree[j]] += 1
			while len(count) >= 3:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			res = max(res, j - i + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(i, j) = (0, 0)
		max_fruit = 0
		baskets = defaultdict(int)
		while j <= len(tree) and i < len(tree):
			if j < len(tree) and len(set(list(baskets.keys()) + [tree[j]])) <= 2:
				baskets[tree[j]] += 1
				j += 1
			else:
				baskets[tree[i]] -= 1
				if baskets[tree[i]] == 0:
					baskets.pop(tree[i])
				i += 1
			max_fruit = max(sum(baskets.values()), max_fruit)
		return max_fruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		maxCol = 0
		baskets = [0, 0]
		while i < len(tree) and maxCol + i < len(tree):
			baskets[0] = tree[i]
			j = i + 1
			basket1Empty = True
			while j < len(tree):
				if tree[j] != baskets[0] and basket1Empty:
					baskets[1] = tree[j]
					basket1Empty = False
				elif tree[j] != baskets[0] and tree[j] != baskets[1]:
					col = j - i
					if col > maxCol:
						maxCol = col
					break
				j += 1
			col = j - i
			if col > maxCol:
				maxCol = col
			i += 1
		return maxCol


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 0:
			return 0
		types = {}
		numFruits = 0
		maxNumFruits = 0
		left = 0
		right = 0
		while right < len(tree):
			if tree[right] in types:
				types[tree[right]] += 1
			else:
				types[tree[right]] = 1
			numFruits += 1
			right += 1
			while len(types) > 2:
				if types[tree[left]] == 1:
					del types[tree[left]]
				else:
					types[tree[left]] -= 1
				left += 1
				numFruits -= 1
			maxNumFruits = max(maxNumFruits, numFruits)
		return maxNumFruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) <= 2:
			return len(tree)
		n = len(tree)
		(res, l) = (0, 0)
		while l < n:
			(type1, type2) = (-1, -1)
			next_l = -1
			for r in range(l, n):
				if type1 == -1:
					type1 = tree[r]
				elif tree[r] != type1 and type2 == -1:
					next_l = r
					type2 = tree[r]
				elif tree[r] != type1 and tree[r] != type2:
					break
				r += 1
			res = max(res, r - l)
			if r == n:
				break
			l = next_l
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		hMap = {}
		if not tree:
			return 0
		maxCount = 0
		count = 0
		for i in range(len(tree)):
			hMap[tree[i]] = i
			if len(hMap) <= 2:
				count += 1
				maxCount = max(count, maxCount)
			else:
				j = sys.maxsize
				r = None
				for k in hMap:
					if hMap[k] < j:
						r = k
						j = hMap[k]
				hMap.pop(r, None)
				count = i - j
		return maxCount


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		counter = {}
		start = 0
		maxL = 0
		for end in range(len(tree)):
			if tree[end] in counter:
				counter[tree[end]] += 1
			else:
				counter[tree[end]] = 1
			while len(counter) > 2:
				counter[tree[start]] -= 1
				if counter[tree[start]] == 0:
					del counter[tree[start]]
				start += 1
			maxL = max(maxL, end - start + 1)
		return maxL


class Solution:

	def totalFruit(self, f: List[int]) -> int:
		(start, count, maxFruits) = (0, 0, 0)
		fruitHash = defaultdict(int)
		for end in range(len(f)):
			if fruitHash[f[end]] == 0:
				count += 1
			fruitHash[f[end]] += 1
			if count <= 2:
				maxFruits = max(maxFruits, end - start + 1)
			while count > 2:
				fruitHash[f[start]] -= 1
				start += 1
				if fruitHash[f[start - 1]] == 0:
					count -= 1
					maxFruits = max(maxFruits, end - start + 1)
		return maxFruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_len = 0
		start = end = 0
		N = len(tree)
		count = 0
		uniq = {}
		while end < N:
			cur = tree[end]
			if cur not in uniq:
				uniq[cur] = 0
			uniq[cur] += 1
			if uniq[cur] == 1:
				count += 1
			while count > 2:
				rem = tree[start]
				uniq[rem] -= 1
				if uniq[rem] == 0:
					count -= 1
				start += 1
			max_len = max(max_len, end - start + 1)
			end += 1
		return max_len


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		k = 2
		start = 0
		freqHashmap = {}
		maxFruit = 0
		for end in range(len(tree)):
			freqHashmap[tree[end]] = freqHashmap.get(tree[end], 0) + 1
			while len(freqHashmap) > k:
				freqHashmap[tree[start]] -= 1
				if freqHashmap[tree[start]] == 0:
					del freqHashmap[tree[start]]
				start += 1
			maxFruit = max(maxFruit, end - start + 1)
		return maxFruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		k = 2
		n = len(tree)
		if n < k:
			return n
		i = 0
		lookup = {}
		ans = 0
		for j in range(n):
			lookup[tree[j]] = j
			if len(lookup) <= k:
				ans = max(ans, j - i + 1)
			else:
				i_min = min(lookup.values())
				del lookup[tree[i_min]]
				i = i_min + 1
		return ans


class Solution:

	def totalFruit(self, tree):
		res = cur = count_b = a = b = 0
		for c in tree:
			cur = cur + 1 if c in (a, b) else count_b + 1
			count_b = count_b + 1 if c == b else 1
			if b != c:
				(a, b) = (b, c)
			res = max(res, cur)
		return res


class Solution:

	def totalFruit(self, tree) -> int:
		if len(tree) < 3:
			return len(tree)
		seq_len = [[tree[0], 0]]
		for f in tree:
			if seq_len[-1][0] == f:
				seq_len[-1][1] += 1
			else:
				seq_len.append([f, 1])
		most = seq_len[0][1]
		if len(seq_len) > 1:
			curr_two_types = set([seq_len[0][0], seq_len[1][0]])
			most = curr_most = seq_len[0][1] + seq_len[1][1]
			for i in range(2, len(seq_len)):
				if seq_len[i][0] in curr_two_types:
					curr_most += seq_len[i][1]
				else:
					curr_most = seq_len[i][1] + seq_len[i - 1][1]
					curr_two_types = set([seq_len[i][0], seq_len[i - 1][0]])
				most = max(most, curr_most)
		return most


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = 0
		(lo, hi) = (-1, 0)
		seen = {}
		for hi in range(len(tree)):
			if tree[hi] not in seen and len(seen) == 2:
				remove = (float('inf'), None)
				for typ in seen:
					remove = min(remove, (seen[typ], typ))
				lo = seen.pop(remove[1])
			seen[tree[hi]] = hi
			ans = max(ans, hi - lo)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(count, i) = ({}, 0)
		for (j, v) in enumerate(tree):
			count[v] = count.get(v, 0) + 1
			if len(count) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
		return j - i + 1


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_count = pair_count = last_count = 0
		fruit_1 = fruit_2 = last_fruit = None
		for fruit_type in tree:
			if fruit_type == fruit_1:
				pair_count += 1
				if fruit_type == last_fruit:
					last_count += 1
				else:
					last_fruit = fruit_type
					last_count = 1
			elif fruit_type == fruit_2:
				pair_count += 1
				if fruit_type == last_fruit:
					last_count += 1
				else:
					last_fruit = fruit_type
					last_count = 1
			elif fruit_1 == None:
				fruit_1 = last_fruit = fruit_type
				last_count = 1
				pair_count += 1
			elif fruit_2 == None:
				fruit_2 = last_fruit = fruit_type
				last_count = 1
				pair_count += 1
			else:
				fruit_1 = last_fruit
				fruit_2 = last_fruit = fruit_type
				max_count = max(max_count, pair_count)
				pair_count = last_count + 1
				last_count = 1
		return max(max_count, pair_count)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = 0
		past = []
		last = []
		for i in range(len(tree)):
			if len(past) == 0:
				past.append(tree[i])
				last.append(i)
				ans = max(i - last[0] + 1, ans)
				continue
			if len(past) == 1:
				if tree[i] not in past:
					past.append(tree[i])
					last.append(i)
				ans = max(i - last[0] + 1, ans)
				continue
			if tree[i] not in past:
				bt = i - 1
				ele = tree[bt]
				while tree[bt] == ele:
					bt -= 1
				bt += 1
				past = [tree[bt], tree[i]]
				last = [bt, i]
			ans = max(i - last[0] + 1, ans)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		l = 0
		count = {}
		for (r, value) in enumerate(tree):
			count[value] = count.get(value, 0) + 1
			if len(count) > 2:
				count[tree[l]] -= 1
				if count[tree[l]] == 0:
					del count[tree[l]]
				l += 1
		return r - l + 1


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(res, start, distince_count, visited) = (0, 0, 0, [0] * len(tree))
		for (i, c) in enumerate(tree):
			if visited[c] == 0:
				distince_count += 1
			visited[c] += 1
			while distince_count > 2:
				visited[tree[start]] -= 1
				if visited[tree[start]] == 0:
					distince_count -= 1
				start += 1
			res = max(res, i - start + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		n = len(tree)
		dic = {}
		x = 0
		for i in range(n):
			if tree[i] not in dic.keys():
				dic[tree[i]] = 1
			else:
				dic[tree[i]] += 1
			if len(dic) > 2:
				dic[tree[x]] -= 1
				if dic[tree[x]] == 0:
					del dic[tree[x]]
				x += 1
		return i - x + 1


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		deq = []
		currentTwo = set()
		result = 0
		temp = 0
		for e in tree:
			if len(deq) == 0:
				currentTwo.add(e)
				deq.append((e, 1))
				temp = 1
			elif e in currentTwo:
				if e == deq[-1][0]:
					deq[-1] = (e, deq[-1][1] + 1)
					temp += 1
				else:
					deq.append((e, 1))
					temp += 1
			else:
				previousOne = deq[-1][0]
				currentTwo = set([previousOne, e])
				deq = deq[-1:]
				temp = deq[-1][1]
				deq.append((e, 1))
				temp += 1
			result = max(result, temp)
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		letter_count = collections.defaultdict(int)
		(left, right) = (0, 0)
		while right < len(tree):
			letter_count[tree[right]] += 1
			right += 1
			if len(letter_count) > 2:
				letter_count[tree[left]] -= 1
				if letter_count[tree[left]] == 0:
					del letter_count[tree[left]]
				left += 1
		return right - left


class Solution:

	def totalFruit(self, tree):
		ans = cur = one = two = count_one = count_two = 0
		for i in tree:
			if i not in (one, two):
				cur = count_two + 1
			else:
				cur += 1
			if i != two:
				(one, two) = (two, i)
				count_two = 1
			else:
				count_two += 1
			ans = max(ans, cur)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not len(tree):
			return 0
		count_max = 0
		start = 0
		f_num = tree[0]
		tracking = set()
		tracking.add(f_num)
		last_change = 0
		current_num = tree[0]
		for i in range(1, len(tree)):
			if tree[i] not in tracking:
				if len(tracking) >= 2:
					count_max = max(i - start, count_max)
					tracking.remove(f_num)
					tracking.add(tree[i])
					f_num = current_num
					start = last_change
				else:
					tracking.add(tree[i])
			if tree[i] != current_num:
				last_change = i
				f_num = current_num
				current_num = tree[i]
		count_max = max(len(tree) - start, count_max)
		return count_max


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		basket1 = -1
		basket2 = -1
		max_fruit = 0
		start = 0
		end = 0
		i = 0
		while i < len(tree):
			if tree[i] == basket1 or tree[i] == basket2:
				if tree[i] != tree[i - 1]:
					end = i
				i += 1
				continue
			if basket1 == -1:
				basket1 = tree[i]
				end = i
				i += 1
				continue
			if basket2 == -1:
				basket2 = tree[i]
				end = i
				i += 1
				continue
			print(i)
			print(end)
			weight = i - start
			max_fruit = max(max_fruit, weight)
			i = end
			start = end
			basket1 = -1
			basket2 = -1
		weight = len(tree) - start
		max_fruit = max(max_fruit, weight)
		return max_fruit


class Solution:

	def totalFruit(self, t: List[int]) -> int:
		(st, a, b, a_hi, res, b_hi) = (0, t[0], -1, 0, 0, 0)
		for (i, v) in enumerate(t):
			if v != a and b == -1:
				b = v
				b_hi = i
			elif v == a:
				a_hi = i
			elif v == b:
				b_hi = i
			elif v not in (a, b):
				res = max(res, i - st)
				st_m = min(a_hi, b_hi)
				(a, b, st, a_hi, b_hi) = (t[st_m + 1], v, st_m + 1, max(a_hi, b_hi), i)
		return max(res, len(t) - st)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		dic = {}
		i = 0
		j = 0
		MAX = 1
		if tree == None or len(tree) == 0:
			return None
		while j < len(tree):
			if len(dic) <= 2:
				dic[tree[j]] = j
				j += 1
			if len(dic) > 2:
				mins = len(tree) - 1
				for val in list(dic.values()):
					mins = min(mins, val)
				i = mins + 1
				del dic[tree[mins]]
			MAX = max(MAX, j - i)
		return MAX


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		l = 0
		mp = collections.defaultdict(int)
		fruits = 1
		for i in range(0, len(tree)):
			mp[tree[i]] += 1
			while len(mp) > 2:
				mp[tree[l]] -= 1
				if mp[tree[l]] == 0:
					del mp[tree[l]]
				l += 1
			fruits = max(fruits, i - l + 1)
		return fruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		left = 0
		right = 0
		window = set()
		res = 0
		last_index = collections.defaultdict(int)
		for right in range(len(tree)):
			fruit_type = tree[right]
			last_index[fruit_type] = right
			if tree[right] in window or len(window) < 2:
				window.add(tree[right])
			else:
				window.add(tree[right])
				while len(window) > 2:
					fruit_type = tree[left]
					if left == last_index[fruit_type]:
						window.remove(fruit_type)
					left += 1
			res = max(res, right - left + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		counts = 0
		starts = {}
		start = end = 0
		longest = 0

		def find_earliest(starts):
			earliest = len(tree)
			for key in starts:
				earliest = min(starts[key], earliest)
			return earliest
		while end < len(tree):
			current = tree[end]
			if current in starts:
				starts[current] = end
				end += 1
			elif counts == 2:
				earliest = find_earliest(starts)
				del starts[tree[earliest]]
				start = earliest + 1
				counts -= 1
			else:
				starts[current] = end
				counts += 1
				end += 1
			longest = max(end - start, longest)
		return max(end - start, longest)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		ans = i = 0
		count = collections.defaultdict(int)
		for (j, ftype) in enumerate(tree):
			count[ftype] += 1
			while len(count) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					count.pop(tree[i])
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 0:
			return 0
		(i, j, n_kind, res) = (0, 0, 1, 1)
		cnts = [0] * len(tree)
		cnts[tree[0]] += 1
		while True:
			while n_kind <= 2:
				res = max(res, j - i + 1)
				j += 1
				if j >= len(tree):
					return res
				if cnts[tree[j]] == 0:
					n_kind += 1
				cnts[tree[j]] += 1
			while n_kind > 2:
				cnts[tree[i]] -= 1
				if cnts[tree[i]] == 0:
					n_kind -= 1
				i += 1
		return res


from collections import deque

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxFruits = 0
		fruitTypes = set()
		queue = deque()
		for i in tree:
			if i in fruitTypes or len(fruitTypes) < 2:
				fruitTypes.add(i)
			else:
				prevFruit = queue[-1]
				j = len(queue) - 2
				while j >= 0 and queue[j] == prevFruit:
					j -= 1
				while j >= 0:
					queue.popleft()
					j -= 1
				for k in list(fruitTypes):
					if k == prevFruit:
						continue
					else:
						fruitTypes.remove(k)
				fruitTypes.add(i)
			queue.append(i)
			maxFruits = max(len(queue), maxFruits)
		return maxFruits


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(l, res, check) = (0, 0, dict())
		for (i, t) in enumerate(tree):
			check[t] = check.get(t, 0) + 1
			if len(check) <= 2:
				res = max(res, i - l + 1)
			while len(check) > 2:
				check[tree[l]] -= 1
				if check[tree[l]] == 0:
					del check[tree[l]]
				l += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) <= 2:
			return len(tree)
		collection_list = [tree[0]]
		counter = 1
		_max = 1
		rep = 1
		for i in range(1, len(tree)):
			if tree[i] in collection_list:
				if tree[i] == tree[i - 1]:
					rep += 1
				else:
					rep = 1
				counter += 1
				if counter > _max:
					_max = counter
			elif len(collection_list) == 1:
				collection_list.append(tree[i])
				counter += 1
				rep = 1
				if counter > _max:
					_max = counter
			else:
				collection_list = [tree[i - 1], tree[i]]
				counter = 1 + rep
				rep = 1
		return _max


from collections import Counter

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		d = collections.defaultdict(int)
		left = 0
		total = 0
		for (idx, i) in enumerate(tree):
			d[i] += 1
			while len(d) > 2:
				d[tree[left]] -= 1
				if d[tree[left]] == 0:
					del d[tree[left]]
				left += 1
			total = max(total, idx - left + 1)
		return total


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 0 or len(tree) == 1:
			return len(tree)
		A = [-1] * 2
		B = [-1] * 2
		f1 = -1
		f2 = -1
		n = len(tree)
		maxi = 1
		i = 0
		while i < n:
			if tree[i] == f1 or tree[i] == f2:
				if tree[i] == f1:
					A[1] = i
				else:
					B[1] = i
			elif tree[i - 1] == f1:
				f2 = tree[i]
				A[0] = B[1] + 1
				B[0] = B[1] = i
			else:
				f1 = tree[i]
				B[0] = A[1] + 1
				A[0] = A[1] = i
			maxi = max(maxi, max(A[1], B[1]) - min(A[0], B[0]))
			i = i + 1
		return maxi + 1


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(idx, baskets, res) = (-1, collections.deque(maxlen=2), 0)
		for (i, x) in enumerate(tree):
			if x not in [y[0] for y in baskets]:
				if len(baskets) == 2:
					(res, idx) = (max(res, i - idx - 1), baskets[0][1])
				baskets.append([x, i])
			elif x == baskets[0][0]:
				baskets.popleft()
				baskets.append([x, i])
			else:
				baskets[1][1] = i
		return max(res, len(tree) - 1 - idx)


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		store = collections.defaultdict(lambda : 0)
		ans = 0
		i = 0
		for (k, val) in enumerate(tree):
			store[val] += 1
			while len(store) > 2:
				store[tree[i]] -= 1
				if store[tree[i]] == 0:
					del store[tree[i]]
				i += 1
			ans = max(ans, k - i + 1)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(f1, f2) = ([-1, -1], [-1, -1])
		(res, fruit1, fruit2) = (0, -1, -1)
		for i in range(len(tree)):
			if tree[i] not in [fruit1, fruit2]:
				if f2[1] > f1[1]:
					f2[0] = f1[1] + 1
					f1 = [i, i]
					fruit1 = tree[i]
				else:
					f1[0] = f2[1] + 1
					f2 = [i, i]
					fruit2 = tree[i]
			elif tree[i] == fruit1:
				f1[1] = i
			else:
				f2[1] = i
			res = max(res, max(f1[1], f2[1]) - min(f1[0], f2[0]))
		return res + 1


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		compressedTree = []
		current = [tree[0], 0]
		for index in range(len(tree)):
			fruit = tree[index]
			if fruit != current[0]:
				compressedTree.append(current)
				current = [fruit, 1]
			else:
				current[1] += 1
		compressedTree.append(current)
		ans = i = 0
		while i < len(compressedTree):
			(types, weight) = (set(), 0)
			for j in range(i, len(compressedTree)):
				types.add(compressedTree[j][0])
				weight += compressedTree[j][1]
				if len(types) >= 3:
					i = j - 1
					break
				ans = max(ans, weight)
			else:
				break
		return ans


from collections import defaultdict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(l, r) = (0, 0)
		d = defaultdict(int)
		res = 0
		for r in range(len(tree)):
			d[tree[r]] += 1
			while len(d) > 2:
				d[tree[l]] -= 1
				if d[tree[l]] == 0:
					d.pop(tree[l])
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		n = len(tree)
		res = 0
		window = defaultdict(int)
		count = 0
		left = 0
		for idx in range(n):
			curr = tree[idx]
			if window[curr] == 0:
				count += 1
			window[curr] += 1
			if count <= 2:
				res = max(res, idx - left + 1)
			while count > 2:
				window[tree[left]] -= 1
				if window[tree[left]] == 0:
					count -= 1
				left += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(count, i, j) = ({}, 0, 0)
		max_cnt = 0
		while j < len(tree):
			v = tree[j]
			count[v] = count.get(v, 0) + 1
			if len(count) <= 2:
				max_cnt = max(sum(count.values()), max_cnt)
			while len(count) > 2:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			j += 1
		return max_cnt


import collections

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		left = 0
		right = 0
		fruitsTypes = defaultdict(int)
		numFruits = 0
		maxNumFruit = 0
		while right < len(tree):
			fruitsTypes[tree[right]] += 1
			numFruits += 1
			right += 1
			while len(fruitsTypes) > 2:
				fruitsTypes[tree[left]] -= 1
				if fruitsTypes[tree[left]] == 0:
					del fruitsTypes[tree[left]]
				numFruits -= 1
				left += 1
			maxNumFruit = max(maxNumFruit, numFruits)
		return maxNumFruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxCount = count = 0
		head = back = 0
		buckets = dict()
		while back < len(tree):
			fruit = tree[back]
			if fruit in buckets:
				buckets[fruit] += 1
			else:
				buckets[fruit] = 1
				while len(list(buckets.keys())) > 2:
					dropFruit = tree[head]
					buckets[dropFruit] -= 1
					if buckets[dropFruit] == 0:
						buckets.pop(dropFruit)
					count -= 1
					head += 1
			count += 1
			maxCount = max(maxCount, count)
			back += 1
		return maxCount


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		result = 0
		(left, right) = (0, 0)
		basket = collections.defaultdict(int)
		while right < len(tree):
			basket[tree[right]] += 1
			while len(basket) > 2:
				if basket[tree[left]] == 1:
					basket.pop(tree[left])
				else:
					basket[tree[left]] -= 1
				left += 1
			result = max(result, right - left + 1)
			right += 1
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		blocks = []
		i = 0
		while i < len(tree):
			j = i + 1
			length = 1
			while j < len(tree) and tree[j] == tree[j - 1]:
				length += 1
				j += 1
			blocks.append((tree[i], length))
			i = j
		maxi = 0
		i = 0
		while i < len(blocks):
			(types, cur) = (set(), 0)
			for j in range(i, len(blocks)):
				types.add(blocks[j][0])
				cur += blocks[j][1]
				if len(types) > 2:
					i = j - 1
					break
				maxi = max(maxi, cur)
			else:
				break
		return maxi


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(i, j) = (0, 0)
		res = 0
		d = {}
		while j < len(tree):
			d[tree[j]] = d.get(tree[j], 0) + 1
			if len(d) <= 2:
				res = max(res, j - i + 1)
			else:
				while len(d) > 2:
					d[tree[i]] = d[tree[i]] - 1
					if d[tree[i]] == 0:
						d.pop(tree[i])
					i += 1
			j += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		t1 = t2 = -1
		t1s = -1
		ans = 0
		for i in range(0, len(tree)):
			t = tree[i]
			if t != t1 and t != t2:
				ans = max(ans, i - t1s)
				t1s = i
				while t1s > 0 and tree[t1s - 1] == tree[i - 1]:
					t1s -= 1
				t1 = tree[i - 1]
				t2 = t
		ans = max(ans, len(tree) - t1s)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		block = []
		prev = tree[0]
		start = 0
		for i in range(1, len(tree)):
			if prev != tree[i]:
				block.append((prev, i - start))
				start = i
				prev = tree[i]
		block.append((prev, len(tree) - start))
		(head, tail) = (0, 1)
		basket = {block[0][0]: block[0][1]}
		res = block[0][1]
		while tail < len(block):
			(t, q) = block[tail]
			if t in list(basket.keys()):
				basket[t] += q
			elif len(basket) < 2:
				basket[t] = q
			else:
				while len(basket) == 2:
					(ht, hq) = block[head]
					head += 1
					basket[ht] -= hq
					if basket[ht] == 0:
						basket.pop(ht)
				basket[t] = q
			val = 0
			for tt in list(basket.keys()):
				val += basket[tt]
			res = max(res, val)
			tail += 1
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		i = 0
		j = 0
		my_map = {}
		max_len = 0
		while i < len(tree):
			while i < len(tree) and (tree[i] not in my_map and len(my_map) < 2 or tree[i] in my_map):
				if tree[i] not in my_map:
					my_map[tree[i]] = 0
				my_map[tree[i]] += 1
				i += 1
			max_len = max(max_len, i - j)
			while len(my_map) == 2:
				my_map[tree[j]] -= 1
				if my_map[tree[j]] == 0:
					del my_map[tree[j]]
				j += 1
		return max_len


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		fruits = {}
		maxNum = 0
		left = 0
		right = 0
		while right < len(tree):
			while len(fruits) < 3 and right < len(tree):
				fruit = tree[right]
				if fruit not in fruits:
					fruits[fruit] = 0
				fruits[fruit] += 1
				if len(fruits) < 3:
					maxNum = max(maxNum, sum(fruits.values()))
				right += 1
			while len(fruits) > 2 and left < right:
				fruit = tree[left]
				fruits[fruit] -= 1
				if fruits[fruit] == 0:
					del fruits[fruit]
				left += 1
		return maxNum


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if len(tree) == 1:
			return 1
		lo = 0
		hi = 1
		baskets = set()
		baskets.add(tree[0])
		bmaps = {}
		bmaps[tree[0]] = 1
		cnt = 1
		while hi < len(tree):
			baskets.add(tree[hi])
			if tree[hi] in bmaps:
				bmaps[tree[hi]] += 1
			else:
				bmaps[tree[hi]] = 1
			while len(baskets) > 2:
				if bmaps[tree[lo]] == 1:
					baskets.remove(tree[lo])
					bmaps[tree[lo]] = 0
				else:
					bmaps[tree[lo]] -= 1
				lo += 1
			cnt = max(hi - lo + 1, cnt)
			hi += 1
		return cnt


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(l, nums, res) = (0, collections.Counter(), 0)
		for r in range(len(tree)):
			nums[tree[r]] += 1
			while len(nums) > 2:
				nums[tree[l]] -= 1
				if not nums[tree[l]]:
					nums.pop(tree[l])
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		if not tree:
			return 0
		i = 0
		max_value = 0
		count = Counter()
		for (index, value) in enumerate(tree):
			count[value] += 1
			while len(count) >= 3:
				count[tree[i]] -= 1
				if count[tree[i]] == 0:
					del count[tree[i]]
				i += 1
			max_value = max(max_value, index - i + 1)
		return max_value


class Solution:

	def totalFruit(self, s: List[int]) -> int:
		m = 0
		arr = {}
		i = 0
		k = 2
		for j in range(len(s)):
			if s[j] not in arr:
				arr[s[j]] = 0
			arr[s[j]] += 1
			while len(arr) > k:
				x = s[i]
				arr[x] -= 1
				if arr[x] == 0:
					arr.pop(x)
				i += 1
			m = max(m, j - i + 1)
		return m


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		blocks = []
		i = 0
		while i < len(tree):
			start = i
			while i + 1 < len(tree) and tree[i + 1] == tree[start]:
				i += 1
			blocks.append((tree[start], i - start + 1))
			i = i + 1
		ans = 0
		i = 0
		while i < len(blocks):
			types = set()
			weight = 0
			j = i
			while j < len(blocks):
				types.add(blocks[j][0])
				weight += blocks[j][1]
				if len(types) > 2:
					i = j - 1
					break
				ans = max(ans, weight)
				j += 1
				if j == len(blocks):
					i = j
			if i == len(blocks):
				break
		return ans


class Solution:

	def total(self, fruits):
		total = 0
		for key in fruits:
			total += fruits[key]
		return total

	def totalFruit(self, tree: List[int]) -> int:
		fruits = {}
		left_index = 0
		best = 0
		for right_index in range(len(tree)):
			curr_fruit = tree[right_index]
			if curr_fruit not in fruits:
				fruits[curr_fruit] = 1
			else:
				fruits[curr_fruit] += 1
			while len(fruits) > 2:
				old_fruit = tree[left_index]
				fruits[old_fruit] -= 1
				if fruits[old_fruit] == 0:
					del fruits[old_fruit]
				left_index += 1
			best = max(best, self.total(fruits))
		return best


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		result = 0
		ptr = 0
		count = collections.Counter()
		for (i, t) in enumerate(tree):
			count[t] += 1
			while len(count) >= 3:
				count[tree[ptr]] -= 1
				if count[tree[ptr]] == 0:
					del count[tree[ptr]]
				ptr += 1
			result = max(result, i - ptr + 1)
		return result


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		max_len = 0
		basket = collections.Counter()
		start = 0
		for (end, fruit) in enumerate(tree):
			basket[fruit] += 1
			while len(basket) >= 3:
				basket[tree[start]] -= 1
				if basket[tree[start]] == 0:
					del basket[tree[start]]
				start += 1
			max_len = max(max_len, end - start + 1)
		return max_len


class Solution:

	def atMostK(self, nums, K):
		counter = collections.Counter()
		res = i = 0
		for j in range(len(nums)):
			if counter[nums[j]] == 0:
				K -= 1
			counter[nums[j]] += 1
			while K < 0:
				counter[nums[i]] -= 1
				if counter[nums[i]] == 0:
					K += 1
				i += 1
			res = max(res, j - i + 1)
		return res

	def totalFruit(self, tree: List[int]) -> int:
		return self.atMostK(tree, 2)


class Solution(object):

	def totalFruit(self, tree):
		n = len(tree)
		(left, right) = (0, 0)
		basket = {}
		ans = 0
		while right < n:
			while left < right and len(basket) > 1:
				basket.update({tree[left]: basket.get(tree[left], 0) - 1})
				if basket.get(tree[left], None) == 0:
					basket.pop(tree[left])
				left += 1
			basket.update({tree[right]: basket.get(tree[right], 0) + 1})
			right += 1
			while right < n and basket.get(tree[right], 0) > 0:
				basket.update({tree[right]: basket.get(tree[right], 0) + 1})
				right += 1
			ans = max(ans, right - left)
		return ans


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		N = len(tree)
		cache = Counter()
		left = right = 0
		maxx = 0
		while left < N and right < N:
			curr = tree[right]
			cache[curr] += 1
			while len(cache) > 2 and left < N:
				curr = tree[left]
				cache[curr] -= 1
				if cache[curr] <= 0:
					del cache[curr]
				left += 1
			maxx = max(maxx, right - left + 1)
			right += 1
		return maxx


from collections import defaultdict

class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		maxAmountOfFruit = 0
		(startIndex, endIndex) = (0, 0)
		countByFruit = defaultdict(int)
		countByFruit[tree[startIndex]] = 1
		while endIndex < len(tree):
			while len(countByFruit) > 2:
				fruitToRemove = tree[startIndex]
				countByFruit[fruitToRemove] -= 1
				if countByFruit[fruitToRemove] == 0:
					del countByFruit[fruitToRemove]
				startIndex += 1
			maxAmountOfFruit = max(maxAmountOfFruit, endIndex - startIndex + 1)
			endIndex += 1
			if endIndex != len(tree):
				countByFruit[tree[endIndex]] += 1
		return maxAmountOfFruit


class Solution:

	def totalFruit(self, tree: List[int]) -> int:
		(left, right) = (0, 0)
		res = 0
		cnt = collections.defaultdict(int)
		while right < len(tree):
			cnt[tree[right]] += 1
			while len(cnt) > 2:
				cnt[tree[left]] -= 1
				if cnt[tree[left]] == 0:
					del cnt[tree[left]]
				left += 1
			res = max(res, right - left + 1)
			right += 1
		return res