Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.
Given an integer array rains where:

rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.
Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)
 
Example 1:
Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:
Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:
Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:
Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:
Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

 
Constraints:

1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		fullLake = {}
		dry = {}
		for (day, lake) in enumerate(rains):
			if lake not in fullLake:
				if lake:
					fullLake[lake] = day
			elif lake:
				dry[fullLake[lake]] = day
				fullLake[lake] = day
		heap = []
		for (day, lake) in enumerate(rains):
			if heap and day >= heap[0][0]:
				return []
			if lake:
				if day in dry:
					heapq.heappush(heap, (dry[day], lake))
				rains[day] = -1
			elif heap:
				rains[day] = heapq.heappop(heap)[1]
			else:
				rains[day] = 1
		return rains


from heapq import heappush, heappop

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		d = collections.defaultdict(list)
		last = []
		for (idx, lake) in enumerate(rains):
			d[lake].append(idx)
		ans = []
		for (idx, lake) in enumerate(rains):
			if lake:
				if last and last[0] == idx:
					return []
				arr = d[lake]
				arr.pop(0)
				if arr:
					heappush(last, arr[0])
				ans.append(-1)
			elif last:
				ans.append(rains[heappop(last)])
			else:
				ans.append(1)
		return ans


from sortedcontainers import SortedSet

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		could_dry = SortedSet()
		last_rain = {}
		dry = {}
		for (idx, rain) in enumerate(rains):
			if rain == 0:
				could_dry.add(idx)
			elif rain not in last_rain:
				last_rain[rain] = idx
			else:
				i = could_dry.bisect_left(last_rain[rain])
				if i == len(could_dry):
					return []
				else:
					day = could_dry[i]
					dry[day] = rain
					could_dry.remove(day)
				last_rain[rain] = idx
		res = []
		for (idx, rain) in enumerate(rains):
			if rain == 0:
				res.append(dry.get(idx, 1))
			else:
				res.append(-1)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		nearest = []
		locs = collections.defaultdict(collections.deque)
		res = [-1] * len(rains)
		for (i, lake) in enumerate(rains):
			locs[lake].append(i)
		for (i, lake) in enumerate(rains):
			if nearest and nearest[0] == i:
				return []
			if lake != 0:
				locs[lake].popleft()
				if locs[lake]:
					nxt = locs[lake][0]
					heapq.heappush(nearest, nxt)
			elif not nearest:
				res[i] = 1
			else:
				next_wet_day = heapq.heappop(nearest)
				wet_lake = rains[next_wet_day]
				res[i] = wet_lake
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		closest = []
		locations = collections.defaultdict(collections.deque)
		for (index, lake) in enumerate(rains):
			locations[lake].append(index)
		res = []
		for (index, lake) in enumerate(rains):
			if closest and closest[0] == index:
				return []
			if not lake:
				if not closest:
					res.append(1)
					continue
				nxt = heapq.heappop(closest)
				res.append(rains[nxt])
			else:
				l = locations[lake]
				l.popleft()
				if l:
					nxt = l[0]
					heapq.heappush(closest, nxt)
				res.append(-1)
		return res


from collections import deque, defaultdict
import heapq

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		rq = defaultdict(deque)
		for (i, r) in enumerate(rains):
			rq[r].append(i)
		for (r, q) in list(rq.items()):
			q.popleft()
		ans = [-1] * len(rains)
		urgent = []
		for (i, r) in enumerate(rains):
			if r != 0:
				q = rq[r]
				if q:
					heapq.heappush(urgent, q.popleft())
			elif urgent:
				d = heapq.heappop(urgent)
				if d < i:
					return []
				ans[i] = rains[d]
			else:
				ans[i] = 1
		return ans if not urgent else []


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = {}
		dries = []
		res = []
		for (i, rain) in enumerate(rains):
			if rain == 0:
				dries.append(i)
				res.append(1)
			else:
				if rain in lakes:
					if len(dries) == 0:
						return []
					idx = bisect_left(dries, lakes[rain])
					if idx == len(dries):
						return []
					res[dries.pop(idx)] = rain
				lakes[rain] = i
				res.append(-1)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = {}
		dries = []
		res = [-1] * len(rains)
		for (i, rain) in enumerate(rains):
			if rain == 0:
				if lakes:
					dries.append(i)
				else:
					res[i] = 1
			elif rain in lakes:
				if len(dries) == 0:
					return []
				idx = bisect_right(dries, lakes[rain])
				if idx == len(dries):
					return []
				res[dries.pop(idx)] = rain
				lakes[rain] = i
			else:
				lakes[rain] = i
		for d in dries:
			if lakes:
				res[d] = lakes.popitem()[0]
			else:
				res[d] = 1
		return res


from collections import defaultdict, deque
import heapq

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		res = [-1] * len(rains)
		dic = defaultdict(deque)
		for (idx, rain) in enumerate(rains):
			dic[rain].append(idx)
		pq = []
		full = set()
		for i in range(len(rains)):
			if rains[i]:
				if rains[i] in full:
					return []
				else:
					full.add(rains[i])
					dic[rains[i]].popleft()
				if dic[rains[i]]:
					heapq.heappush(pq, dic[rains[i]][0])
			elif not pq:
				res[i] = 1
			else:
				lake = rains[heapq.heappop(pq)]
				res[i] = lake
				full.discard(lake)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		(floods, n, visited, water_heap) = (None, len(rains), defaultdict(int), [])
		for i in range(n - 1, -1, -1):
			if rains[i]:
				if rains[i] in visited:
					floods = (i, visited[rains[i]], floods)
				visited[rains[i]] = i
		for i in range(n):
			if not rains[i]:
				while floods and floods[0] < i:
					(start, end, floods) = floods
					heapq.heappush(water_heap, (end, start))
				if not water_heap:
					rains[i] = 1
				else:
					(end, start) = heappop(water_heap)
					if end < i:
						return []
					rains[i] = rains[end]
			else:
				rains[i] = -1
		if water_heap or floods:
			return []
		return rains


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		full = set()
		priority = []
		toReturn = []
		for i in rains:
			if i != 0:
				if i in full:
					priority.append(i)
				else:
					full.add(i)
		full = set()
		for i in rains:
			if i == 0:
				done = False
				for x in range(len(priority)):
					if priority[x] in full:
						a = priority.pop(x)
						toReturn.append(a)
						full.remove(a)
						done = True
						break
				if not done:
					toReturn.append(1)
			elif i in full:
				return []
			else:
				full.add(i)
				toReturn.append(-1)
		return toReturn


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		N = len(rains)
		ans = [-1] * N
		drydays = []
		last = {}
		for (i, e) in enumerate(rains):
			if e == 0:
				drydays += (i,)
			else:
				if e in last:
					lastIndex = last[e]
					j = bisect_right(drydays, lastIndex)
					if j < len(drydays):
						ans[drydays[j]] = e
						del drydays[j]
					else:
						return []
				last[e] = i
		for d in drydays:
			ans[d] = 1
		return ans


def avoid(rains):
	zeros = []
	full = {}
	sol = [-1] * len(rains)
	for (ix, r) in enumerate(rains):
		if r == 0:
			zeros.append(ix)
		elif r not in full:
			full[r] = ix
		else:
			if not zeros:
				return []
			zix = None
			rix = full[r]
			for i in range(len(zeros)):
				if zeros[i] > rix:
					zix = zeros.pop(i)
					break
			if not zix:
				return []
			sol[zix] = r
			full[r] = ix
	while zeros:
		sol[zeros.pop()] = 1
	return sol

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		return avoid(rains)


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = [-1] * len(rains)
		lake_to_days = collections.defaultdict(list)
		full_lakes = set()
		to_empty = []
		for (day, lake) in enumerate(rains):
			lake_to_days[lake].append(day)
		for day in range(len(rains)):
			lake = rains[day]
			if lake:
				if lake in full_lakes:
					return []
				full_lakes.add(lake)
				lake_to_days[lake].pop(0)
				if lake_to_days[lake]:
					heapq.heappush(to_empty, lake_to_days[lake][0])
			elif to_empty:
				ans[day] = rains[heapq.heappop(to_empty)]
				full_lakes.remove(ans[day])
			else:
				ans[day] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		fill = {}
		dry = []
		ans = [0] * len(rains)
		for (i, v) in enumerate(rains):
			if v == 0:
				dry.append(i)
				continue
			if v not in fill:
				fill[v] = i
				ans[i] = -1
			elif v in fill:
				idx = bisect.bisect_left(dry, fill[v])
				if idx == len(dry):
					return []
				else:
					ans[dry[idx]] = v
					dry.pop(idx)
				fill[v] = i
				ans[i] = -1
		for i in range(len(ans)):
			if ans[i] == 0:
				ans[i] = 1
		return ans


import heapq

def drying_strategy(rains):
	last_rain = {}
	chain_rain = {}
	for (time, rain) in enumerate(rains):
		if rain > 0:
			if rain in last_rain:
				chain_rain[last_rain[rain]] = time
			last_rain[rain] = time
	del last_rain
	urgency = []
	filled = set()
	solution = []
	for (time, rain) in enumerate(rains):
		if rain > 0:
			if rain in filled:
				return []
			else:
				filled.add(rain)
				if time in chain_rain:
					heapq.heappush(urgency, chain_rain[time])
			solution.append(-1)
		else:
			solved = False
			while not solved:
				if not urgency:
					solution.append(1)
					if 1 in filled:
						filled.remove(1)
					solved = True
				else:
					time = heapq.heappop(urgency)
					rain = rains[time]
					if rain not in filled:
						pass
					else:
						solution.append(rain)
						filled.remove(rain)
						solved = True
	return solution

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		return drying_strategy(rains)


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		dic = collections.defaultdict(list)
		for (day, lake) in enumerate(rains):
			dic[lake].append(day)
		res = [-1] * len(rains)
		to_empty = []
		for i in range(len(rains)):
			lake = rains[i]
			if lake:
				if dic[lake] and dic[lake][0] < i:
					return []
				if dic[lake] and len(dic[lake]) > 1:
					heapq.heappush(to_empty, dic[lake][1])
			elif to_empty:
				res[i] = rains[heapq.heappop(to_empty)]
				dic[res[i]].pop(0)
			else:
				res[i] = 1
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		output = [-1] * len(rains)
		dic = dict()
		stack = []
		for (i, n) in enumerate(rains):
			if n == 0:
				stack.append(i)
			elif n not in dic:
				dic[n] = i
			else:
				if not stack:
					return []
				for j in stack:
					if j > dic[n]:
						break
				if j < dic[n]:
					return []
				stack.pop(stack.index(j))
				output[j] = n
				dic[n] = i
		for j in stack:
			output[j] = 1
		return output


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		res = []
		free_day = []
		filled = {}
		for (day, city) in enumerate(rains):
			if city:
				res.append(-1)
				if city not in filled:
					filled[city] = day
				elif free_day and free_day[-1] > filled[city]:
					dry_day = bisect.bisect_left(free_day, filled[city])
					res[free_day.pop(dry_day)] = city
					filled[city] = day
				else:
					return []
			else:
				res.append(1)
				free_day.append(day)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		n = len(rains)
		ans = [-1] * n
		last = {}
		dry_days = []
		for (idx, r) in enumerate(rains):
			if r == 0:
				dry_days.append(idx)
			else:
				if r in last:
					found = False
					j = 0
					while j < len(dry_days):
						if dry_days[j] > last[r]:
							ans[dry_days[j]] = r
							found = True
							break
						j += 1
					if not found:
						return []
					dry_days.pop(j)
				last[r] = idx
		while dry_days:
			dry_day = dry_days.pop()
			ans[dry_day] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = [-1] * len(rains)
		nearest = []
		locs = defaultdict(deque)
		for (i, lake) in enumerate(rains):
			locs[lake].append(i)
		for (i, lake) in enumerate(rains):
			if nearest and nearest[0] == i:
				return []
			if lake == 0:
				if not nearest:
					ans[i] = 1
				else:
					n = heappop(nearest)
					ans[i] = rains[n]
			else:
				locs[lake].popleft()
				if locs[lake]:
					heappush(nearest, locs[lake][0])
		return ans


from collections import Counter, defaultdict, OrderedDict, deque
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from typing import List
import itertools
import math
import heapq
import string
true = True
false = False
(MIN, MAX, MOD) = (-1061109567, 1061109567, 1000000007)

class DisjointSet:

	def __init__(self, size=10):
		self.data = list(range(size))

	def find(self, i):
		if i == self.data[i]:
			return i
		else:
			j = self.find(self.data[i])
			self.data[i] = j
			return j

	def merge(self, i):
		self.data[i] = i + 1

class Solution:

	def method2(self, rains: List[int]) -> List[int]:
		n = len(rains)
		cc = {}
		ds = DisjointSet(n)
		i = 0
		while i < n:
			if rains[i] == 0:
				rains[i] = 1
			else:
				lake = rains[i]
				if lake in cc:
					available_dry_day = ds.find(cc[lake])
					if available_dry_day < i:
						rains[available_dry_day] = lake
						ds.merge(available_dry_day)
					else:
						return []
				cc[lake] = i
				ds.merge(i)
				rains[i] = -1
			i += 1
		return rains

	def avoidFlood(self, rains: List[int]) -> List[int]:
		return self.method2(rains)
		n = len(rains)
		cc = defaultdict(int)
		dry = list()
		res = []
		for (i, r) in enumerate(rains):
			if r == 0:
				dry.append(i)
				res.append(1)
			else:
				if r not in cc:
					cc[r] = i
				else:
					last_idx = cc[r]
					j = bisect_left(dry, last_idx)
					if j == len(dry):
						return []
					day = dry[j]
					del dry[j]
					res[day] = r
					cc[r] = i
				res.append(-1)
		return res
sol = Solution()
rains = [1, 2, 3, 4]
rains = [69, 0, 0, 0, 69]
rains = [1, 0, 2, 3, 0, 1, 2]
rains = [1, 2, 0, 0, 2, 1]


import heapq
from collections import deque, defaultdict

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ret = [-1 for i in rains]
		rain_days = defaultdict(deque)
		for (i, lake) in enumerate(rains):
			if lake != 0:
				rain_days[lake].append(i)
		to_drain = []
		for (i, lake) in enumerate(rains):
			if lake == 0:
				if len(to_drain) == 0:
					ret[i] = 1
				else:
					(day, lake) = heapq.heappop(to_drain)
					if day < i:
						return []
					ret[i] = lake
			elif len(rain_days[lake]) > 1:
				rain_days[lake].popleft()
				heapq.heappush(to_drain, (rain_days[lake][0], lake))
		if len(to_drain) > 0:
			return []
		return ret


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = defaultdict(deque)
		for (day, lake) in enumerate(rains):
			lakes[lake].append(day)
		N = len(rains)
		res = [1] * N
		heap = []
		for (day, lake) in enumerate(rains):
			if lake:
				lakes[lake].popleft()
				if lakes[lake]:
					next_lake_day = lakes[lake][0]
					heappush(heap, next_lake_day)
				res[day] = -1
			elif heap:
				chosen_day = heappop(heap)
				if chosen_day < day:
					return []
				res[day] = rains[chosen_day]
		return res if not heap else []


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		n = len(rains)
		res = [-1] * n
		dry = []
		rained = {}
		for (i, r) in enumerate(rains):
			if r:
				if r not in rained:
					rained[r] = i
				elif not dry:
					return []
				else:
					idx = bisect.bisect_left(dry, rained[r])
					if idx == len(dry):
						return []
					res[dry[idx]] = r
					dry.pop(idx)
					rained[r] = i
			else:
				dry.append(i)
		for i in dry:
			res[i] = 1
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		a = rains
		n = len(a)
		j = 0
		ans = [-1] * n
		v = {}
		q = []
		for i in range(n):
			c = a[i]
			if c:
				if c in v:
					j = bisect.bisect(q, v[c])
					if j == len(q):
						return []
					else:
						ans[q[j]] = c
						q.pop(j)
				v[c] = i
			else:
				q.append(i)
		while q:
			ans[q.pop()] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		from collections import defaultdict, deque
		closest = []
		locs = defaultdict(deque)
		res = []
		for (i, lake) in enumerate(rains):
			locs[lake].append(i)
		for (i, rain) in enumerate(rains):
			if closest and closest[0] == i:
				return []
			if rain:
				locs[rain].popleft()
				if locs[rain]:
					heapq.heappush(closest, locs[rain][0])
				res.append(-1)
			elif closest:
				dry = heapq.heappop(closest)
				res.append(rains[dry])
			else:
				res.append(1)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakesFull = {}
		n = len(rains)
		dry = []
		res = []
		for i in range(n):
			l = rains[i]
			if l == 0:
				dry.append(i)
				res.append(-10000000)
				continue
			else:
				if l in lakesFull:
					if len(dry) > 0:
						di = -1
						for dd in range(len(dry)):
							if dry[dd] > lakesFull[l]:
								di = dry[dd]
								dry.pop(dd)
								break
						if di >= 0:
							res[di] = l
							del lakesFull[l]
						else:
							return []
					else:
						return []
				lakesFull[l] = i
				res.append(-1)
		for i in range(n):
			if res[i] == -10000000:
				res[i] = 1
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		full = set()
		drys = []
		filled = {}
		for i in range(len(rains)):
			if not rains[i]:
				drys.append(i)
			else:
				if rains[i] in full:
					if not drys:
						return []
					if drys[-1] < filled[rains[i]]:
						return []
					index = bisect.bisect(drys, filled[rains[i]])
					rains[drys.pop(index)] = rains[i]
				else:
					full.add(rains[i])
				filled[rains[i]] = i
				rains[i] = -1
		rains = [1 if i == 0 else i for i in rains]
		return rains


class Solution:

	def avoidFlood(self, rains):
		(filled, dry_days) = ({}, [])
		ans = [1] * len(rains)
		for (day, lake) in enumerate(rains):
			if not lake:
				dry_days.append(day)
				continue
			ans[day] = -1
			if lake in filled:
				if not dry_days:
					return []
				dry_on_day_index = bisect.bisect_left(dry_days, filled[lake])
				if dry_on_day_index >= len(dry_days):
					return []
				dry_on_day = dry_days.pop(dry_on_day_index)
				ans[dry_on_day] = lake
			filled[lake] = day
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		d = {}
		dry = []
		res = []
		for (day, rain) in enumerate(rains):
			if rain != 0:
				if rain in d:
					p = d[rain]
					flag = -1
					for dry_day in dry:
						if dry_day > p:
							flag = dry_day
							break
					if flag == -1:
						return []
					res[flag] = rain
					dry.remove(flag)
					d[rain] = day
				else:
					d[rain] = day
				res.append(-1)
			else:
				dry.append(day)
				res.append(56)
		return res


from typing import Set, List
from copy import deepcopy
import bisect

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		full_lakes = dict()
		dry_days = list()
		ans = list()
		for (day, lake) in enumerate(rains):
			if lake == 0:
				dry_days.append(day)
				ans.append(1)
			else:
				if lake not in full_lakes:
					full_lakes[lake] = day
				elif dry_days:
					filled_at = full_lakes[lake]
					index = bisect.bisect_right(dry_days, filled_at)
					if index == len(dry_days):
						return list()
					ans[dry_days[index]] = lake
					del dry_days[index]
					full_lakes[lake] = day
				else:
					return list()
				ans.append(-1)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		rains_over_city = {}
		lake_drying_days = []
		ind = 0
		for rain in rains:
			if rain > 0:
				rain_index = rains_over_city.get(rain, -1)
				if rain_index != -1:
					len_lak = len(lake_drying_days)
					j = 0
					while j < len_lak and lake_drying_days[j] <= rain_index:
						j += 1
					if j >= len_lak:
						return []
					rains[lake_drying_days[j]] = rain
					lake_drying_days.remove(lake_drying_days[j])
					rains_over_city.pop(rain)
				rains_over_city[rain] = ind
				rains[ind] = -1
			else:
				lake_drying_days.append(ind)
				rains[ind] = 1
			ind += 1
		return rains


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = []
		zero = []
		full = {}
		for (day, city) in enumerate(rains):
			if city:
				ans.append(-1)
				if city in full:
					if zero and zero[-1] > full[city]:
						dry = bisect.bisect_left(zero, full[city])
						ans[zero.pop(dry)] = city
						full[city] = day
					else:
						return []
				else:
					full[city] = day
			else:
				ans.append(1)
				zero.append(day)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		from collections import deque
		import heapq
		city = {}
		ans = [1] * len(rains)
		for k in range(len(rains)):
			if rains[k]:
				if rains[k] not in city:
					city[rains[k]] = deque()
				city[rains[k]].append(k)
				ans[k] = -1
		option = []
		wet = {}
		for k in range(len(rains)):
			if rains[k]:
				if rains[k] in wet:
					return []
				else:
					wet[rains[k]] = k
					city[rains[k]].popleft()
					if city[rains[k]]:
						heapq.heappush(option, (city[rains[k]][0], rains[k]))
			elif option:
				(_, c) = heapq.heappop(option)
				ans[k] = c
				wet.pop(c)
			else:
				ans[k] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		from bisect import bisect_left
		wet = {}
		ans = [1] * len(rains)
		dry = []
		for k in range(len(rains)):
			if not rains[k]:
				dry.append(k)
			else:
				ans[k] = -1
		for k in range(len(rains)):
			if rains[k] > 0:
				if rains[k] not in wet:
					wet[rains[k]] = k
				else:
					index = bisect_left(dry, wet[rains[k]])
					if index == len(dry) or dry[index] > k:
						return []
					wet[rains[k]] = k
					ans[dry[index]] = rains[k]
					dry.pop(index)
		return ans


from sortedcontainers import SortedList

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		res = [1 for i in range(len(rains))]
		(ls, zs) = ({}, SortedList())
		for (i, l) in enumerate(rains):
			if l in ls:
				if len(zs) == 0:
					return []
				else:
					p = zs.bisect(ls[l])
					if p == len(zs):
						return []
					res[zs[p]] = l
					zs.pop(p)
					res[i] = -1
					ls[l] = i
			elif l != 0:
				ls[l] = i
				res[i] = -1
			else:
				zs.add(i)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:

		def closest(i, arr):
			for j in arr:
				if j > i:
					return j
			return -1
		ans = [1] * len(rains)
		visited = dict()
		zeros = deque()
		x = 0
		while x < len(rains) and rains[x] == 0:
			x += 1
		for i in range(x, len(rains)):
			if rains[i] in visited:
				if not zeros:
					return []
				else:
					r = visited[rains[i]]
					c = closest(r, zeros)
					if c == -1:
						return []
					ans[c] = rains[i]
					zeros.remove(c)
					ans[i] = -1
					visited[rains[i]] = i
			elif rains[i]:
				ans[i] = -1
				visited[rains[i]] = i
			else:
				zeros.append(i)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		from sortedcontainers import SortedList
		wet = {}
		ans = [1] * len(rains)
		dry = SortedList()
		for k in range(len(rains)):
			if not rains[k]:
				dry.add(k)
			else:
				ans[k] = -1
		for k in range(len(rains)):
			if rains[k] > 0:
				if rains[k] not in wet:
					wet[rains[k]] = k
				else:
					index = dry.bisect_left(wet[rains[k]])
					if index == len(dry) or dry[index] > k:
						return []
					wet[rains[k]] = k
					ans[dry[index]] = rains[k]
					dry.pop(index)
		return ans


from collections import deque

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ret = [-1 for i in range(0, len(rains))]
		filled_lakes = dict()
		dry_days = list()
		i = 0
		while i < len(rains):
			rain = rains[i]
			if rain == 0:
				dry_days.append(i)
			if rain > 0 and rain in filled_lakes:
				prev_pos = filled_lakes[rain]
				if len(dry_days) == 0:
					return []
				j = 0
				while j < len(dry_days) and prev_pos > dry_days[j]:
					j += 1
				if j == len(dry_days):
					return []
				k = dry_days.pop(j)
				ret[k] = rain
			if rain != 0:
				filled_lakes[rain] = i
			i += 1
		while len(dry_days) > 0:
			j = dry_days.pop()
			ret[j] = 1
		return ret


from sortedcontainers import SortedList

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = defaultdict(deque)
		for (day, lake) in enumerate(rains):
			lakes[lake].append(day)
		N = len(rains)
		need = SortedList()
		res = [1] * N
		for (curr_day, lake) in enumerate(rains):
			if lake:
				lakes[lake].popleft()
				if len(lakes[lake]) > 0:
					next_lake_index = lakes[lake][0]
					need.add(next_lake_index)
				res[curr_day] = -1
			elif need:
				chosen_lake_index = need.pop(0)
				if chosen_lake_index < curr_day:
					return []
				res[curr_day] = rains[chosen_lake_index]
		return res if not need else []


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		drying = []
		out = []
		lakes = {}
		v = 1
		for (c, i) in enumerate(rains):
			out.append(-1)
			if i <= 0:
				drying.append(c)
			elif i in lakes and drying:
				found = -1
				for (index, val) in enumerate(drying):
					if val > lakes[i]:
						found = index
						break
				if found > -1:
					out[drying.pop(found)] = i
					lakes[i] = c
				else:
					return []
			elif i in lakes:
				return []
			else:
				lakes[i] = c
				v = i
		for j in drying:
			out[j] = v
		return out


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		return_arr = [-1 for i in range(len(rains))]
		rains_dict = {}
		zeros_indices = []
		for i in range(len(rains)):
			if rains[i] == 0:
				return_arr[i] = 1
				zeros_indices.append(i)
			elif rains[i] not in rains_dict:
				rains_dict[rains[i]] = i
			else:
				if len(zeros_indices) == 0:
					return []
				index = 0
				while zeros_indices[index] < rains_dict[rains[i]]:
					index += 1
					print(index)
					if index == len(zeros_indices):
						return []
				return_arr[zeros_indices[index]] = rains[i]
				rains_dict[rains[i]] = i
				del zeros_indices[index]
		return return_arr


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = [-1] * len(rains)
		spares = []
		full = {}
		for i in range(len(rains)):
			if rains[i] > 0:
				if rains[i] in full:
					for j in range(len(spares)):
						if spares[j] > full[rains[i]]:
							ans[spares.pop(j)] = rains[i]
							full[rains[i]] = i
							break
					else:
						return []
				else:
					full[rains[i]] = i
			else:
				spares.append(i)
		for i in spares:
			ans[i] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		sunny_day_idx = []
		res = [-1] * len(rains)
		for (day, lake) in enumerate(rains):
			if lake == 0:
				sunny_day_idx.append(day)
				res[day] = 1
		last_day_rains_over_lake = {}

		def binary_search(sunny_day_idx, prev):
			(low, high) = (0, len(sunny_day_idx))
			while low < high:
				mid = (low + high) // 2
				if sunny_day_idx[mid] > prev:
					high = mid
				else:
					low = mid + 1
			return low if low < len(sunny_day_idx) and sunny_day_idx[low] > prev else None
		print(binary_search([2, 3], 0))
		for (day, lake) in enumerate(rains):
			if lake != 0 and lake not in last_day_rains_over_lake:
				last_day_rains_over_lake[lake] = day
			elif lake != 0 and lake in last_day_rains_over_lake:
				if not sunny_day_idx:
					return []
				idx = binary_search(sunny_day_idx, last_day_rains_over_lake[lake])
				if idx == None:
					return []
				if sunny_day_idx[idx] > day:
					return []
				res[sunny_day_idx[idx]] = lake
				last_day_rains_over_lake[lake] = day
				sunny_day_idx.pop(idx)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		days_next = []
		n = len(rains)
		dct_lk2day = defaultdict(int)
		for (day_rev, e) in enumerate(rains[::-1]):
			if e in dct_lk2day:
				days_next.append(dct_lk2day[e])
			else:
				days_next.append(n)
			dct_lk2day[e] = n - 1 - day_rev
		days_next = days_next[::-1]
		minHp = []
		rst = []
		for (day, lk) in enumerate(rains):
			if not lk:
				if minHp:
					d_next = heappop(minHp)
					rst.append(rains[d_next])
				else:
					rst.append(1)
			elif minHp and day == minHp[0]:
				return []
			else:
				if days_next[day] < n:
					heappush(minHp, days_next[day])
				rst.append(-1)
		return rst


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		q = []
		ans = []
		hashmap = {}
		for i in range(len(rains)):
			if rains[i] == 0:
				q.append(i)
				ans.append(1)
			else:
				if rains[i] in hashmap:
					if len(q) == 0:
						return []
					else:
						index = hashmap[rains[i]]
						pos = bisect.bisect_right(q, index)
						if pos < len(q):
							ans[q[pos]] = rains[i]
							q.pop(pos)
						else:
							return []
				hashmap[rains[i]] = i
				ans.append(-1)
		return ans


from bisect import bisect_left

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = [-1] * len(rains)
		last_appear = {}
		dry_days = []
		for (idx, lake) in enumerate(rains):
			if lake == 0:
				dry_days.append(idx)
				continue
			if lake in last_appear:
				first_0 = bisect_left(dry_days, last_appear[lake])
				if first_0 == len(dry_days):
					return []
				ans[dry_days[first_0]] = lake
				dry_days.pop(first_0)
				last_appear.pop(lake)
			last_appear[lake] = idx
		for day in dry_days:
			ans[day] = 1
		return ans


from sortedcontainers import SortedList

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = [-1] * len(rains)
		zeros = SortedList()
		todry = {}
		for (i, r) in enumerate(rains):
			if r == 0:
				zeros.add(i)
				continue
			if r in todry:
				di = zeros.bisect_left(todry[r])
				if di >= len(zeros):
					return []
				ans[zeros[di]] = r
				zeros.pop(di)
			todry[r] = i
		for i in range(len(rains)):
			if rains[i] == 0 and ans[i] == -1:
				ans[i] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		n = len(rains)
		M = max(rains)
		ans = [-1] * n
		l = set()
		r = collections.defaultdict(list)
		for j in range(n):
			if rains[j] > 0:
				r[rains[j]] += [j]
		i = 0
		tbd = []
		while i < n:
			if rains[i] > 0:
				if rains[i] in l:
					return []
				else:
					l.add(rains[i])
					r[rains[i]].pop(0)
					if len(r[rains[i]]) > 0:
						heapq.heappush(tbd, r[rains[i]][0])
			elif rains[i] == 0:
				if len(tbd) > 0:
					get = heapq.heappop(tbd)
					ans[i] = rains[get]
					l.remove(rains[get])
				else:
					ans[i] = M + 1
			i += 1
		return ans


from bisect import bisect_left

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		flooded = {}
		dry_days = []
		out = [-1 for _ in range(len(rains))]
		for i in range(len(rains)):
			day = rains[i]
			if day > 0:
				if day in flooded:
					if dry_days:
						dry = bisect_left(dry_days, flooded[day])
						if dry == len(dry_days):
							return []
						else:
							dry_day = dry_days.pop(dry)
							out[dry_day] = day
					else:
						return []
				flooded[day] = i
			else:
				dry_days.append(i)
		for dry_day in dry_days:
			out[dry_day] = 1
		return out


from collections import deque

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		zero_indices = deque()
		last_flood = {}
		result = [-1] * len(rains)

		def find_zero_for_lake(idx, r):
			if not zero_indices:
				return None
			for zero_index in zero_indices:
				if last_flood[r] < zero_index < idx:
					return zero_index
			return None
		for (idx, r) in enumerate(rains):
			if r > 0:
				if r in last_flood:
					found_zero = find_zero_for_lake(idx, r)
					if found_zero is None:
						return []
					else:
						result[found_zero] = r
						zero_indices.remove(found_zero)
				last_flood[r] = idx
			else:
				zero_indices.append(idx)
		while zero_indices:
			zero_index = zero_indices.pop()
			result[zero_index] = 1
		return result


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		(full, idxDry, res) = (dict(), [], [-1] * len(rains))
		for (i, x) in enumerate(rains):
			if not x:
				idxDry.append(i)
				continue
			if x in full:
				if not idxDry or full[x] > idxDry[-1]:
					return []
				for idx in idxDry:
					if idx > full[x]:
						res[idx] = x
						idxDry.remove(idx)
						del full[x]
						break
			full[x] = i
		for i in idxDry:
			res[i] = 1
		return res


from bisect import bisect_left

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		filled = {}
		ans = [-1] * len(rains)
		rem = []

		def get(r):
			(low, high) = (0, len(rem) - 1)
			while low <= high:
				mid = low + (high - low) // 2
				if rem[mid] > r:
					low = mid + 1
				else:
					high = mid - 1
			return rem[low] if 0 <= low < len(rem) else -1
		for i in range(len(rains) - 1, -1, -1):
			curr = rains[i]
			if curr == 0:
				rem.append(i)
				continue
			elif curr in filled:
				if not rem:
					return []
				idx = filled.pop(curr)
				zero = get(idx)
				if not i < zero < idx:
					return []
				ans[zero] = curr
				rem.remove(zero)
			filled[curr] = i
		while rem:
			ans[rem.pop()] = 1
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		n = len(rains)
		idx = defaultdict(list)
		for i in range(n):
			if rains[i] > 0:
				idx[rains[i]].append(i)
		nex = defaultdict(lambda : -1)
		for k in idx.keys():
			for i in range(len(idx[k]) - 1):
				nex[idx[k][i]] = idx[k][i + 1]
		cnt = defaultdict(int)
		pq = []
		ans = []
		for i in range(n):
			if rains[i] > 0:
				if cnt[rains[i]] == 1:
					return []
				cnt[rains[i]] = 1
				if nex[i] != -1:
					heappush(pq, (nex[i], rains[i]))
				ans.append(-1)
			elif len(pq) == 0:
				ans.append(1)
			else:
				(_, lake) = heappop(pq)
				cnt[lake] -= 1
				ans.append(lake)
		return ans


class Solution:

	def backtrack(self, rains, full, position, seq):
		if position >= len(rains):
			return True
		if rains[position] > 0:
			if rains[position] in full:
				return False
			seq.append(-1)
			full.add(rains[position])
			if self.backtrack(rains, full, position + 1, seq):
				return True
			full.remove(rains[position])
			seq.pop()
		elif rains[position] == 0:
			for lake in full:
				seq.append(lake)
				full.remove(lake)
				if self.backtrack(rains, full, position + 1, seq):
					return True
				full.add(lake)
				seq.pop()
			if len(full) < 1:
				seq.append(1)
				if self.backtrack(rains, full, position + 1, seq):
					return True
				seq.pop()

	def avoidFloodBacktrack(self, rains: List[int]) -> List[int]:
		seq = []
		full = set()
		if not self.backtrack(rains, full, 0, seq):
			return []
		return seq

	def avoidFlood(self, rains: List[int]) -> List[int]:
		spares = []
		recent = dict()
		full = set()
		ans = []
		for i in range(len(rains)):
			if rains[i] > 0:
				ans.append(-1)
				if rains[i] in full:
					if len(spares) < 1:
						return []
					valid = False
					for d in range(len(spares)):
						dry = spares[d]
						if dry > recent[rains[i]]:
							ans[dry] = rains[i]
							full.remove(rains[i])
							del spares[d]
							valid = True
							break
					if not valid:
						return []
				elif rains[i] in recent and recent[rains[i]] == i - 1:
					return []
				else:
					full.add(rains[i])
				recent[rains[i]] = i
			else:
				ans.append(1)
				spares.append(i)
		return ans
if False:
	assert Solution().avoidFlood([69, 0, 0, 0, 69]) == [-1, 69, 1, 1, -1]
	assert Solution().avoidFlood([1, 2, 0, 0, 2, 1]) == [-1, -1, 2, 1, -1, -1]
	assert Solution().avoidFlood([1, 2, 0, 1, 2]) == []
	assert Solution().avoidFlood([10, 20, 20]) == []


from collections import defaultdict
from sortedcontainers import SortedSet

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:

		def getCeil(a, v):
			if not a:
				return None
			b = a.bisect_right(v)
			if b == 0:
				if a[b] >= v:
					return a[b]
				return None
			if b == len(a):
				return None
			return a[b]
		res = [0] * len(rains)
		zeros = SortedSet()
		m = {}
		for (i, val) in enumerate(rains):
			if val == 0:
				zeros.add(i)
			else:
				if val in m:
					n = getCeil(zeros, m[val])
					print(n)
					if not n:
						return []
					res[n] = val
					zeros.remove(n)
				res[i] = -1
				m[val] = i
		for i in zeros:
			res[i] = 1
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		queue = []
		lakes = dict()
		days = []
		for i in range(len(rains)):
			if rains[i] == 0:
				queue.append(i)
			elif rains[i] in lakes:
				if not queue:
					return []
				for queue_index in range(len(queue)):
					if queue[queue_index] < lakes[rains[i]]:
						if queue_index == len(queue) - 1:
							return []
						continue
					else:
						days[queue.pop(queue_index)] = rains[i]
						break
				lakes[rains[i]] = i
			else:
				lakes[rains[i]] = i
			days.append(-1 if rains[i] != 0 else 999)
		return days


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		res = []
		for rain in rains:
			if rain > 0:
				res.append(-1)
			else:
				res.append(1)
		full_lakes = defaultdict(list)
		sunny_days = []
		start = 0
		end = len(rains) - 1
		while rains[start] == 0:
			start += 1
		while rains[end] == 0:
			end -= 1

		def binarySearch(sunny_days, prev_rain, curr):
			if not sunny_days:
				return -1
			low = 0
			high = len(sunny_days)
			while low < high:
				mid = (low + high) // 2
				if sunny_days[mid] <= prev_rain:
					low = mid + 1
				else:
					high = mid
			if low >= len(sunny_days) or sunny_days[low] <= prev_rain or sunny_days[low] >= curr:
				return -1
			else:
				return low
		for i in range(start, end + 1):
			if rains[i] != 0:
				if rains[i] not in full_lakes or not full_lakes[rains[i]]:
					full_lakes[rains[i]].append(i)
				else:
					prev_rain = full_lakes[rains[i]][-1]
					if not sunny_days:
						return []
					idx = binarySearch(sunny_days, prev_rain, i)
					if idx == -1:
						return []
					else:
						res[sunny_days[idx]] = rains[i]
						full_lakes[rains[i]].pop()
						full_lakes[rains[i]].append(i)
						sunny_days.pop(idx)
			else:
				sunny_days.append(i)
		return res


class Solution:

	def find_min_greater(self, a, x):
		start = 0
		end = len(a) - 1
		while start < end:
			mid = start + end
			mid = mid // 2
			if a[mid] < x and a[mid + 1] > x:
				return mid + 1
			elif a[mid] < x:
				start = mid
			else:
				end = mid
		return start

	def avoidFlood(self, rains: List[int]) -> List[int]:
		last_rained = {}
		no_rain = []
		ans = []
		for i in range(len(rains)):
			if rains[i] == 0:
				no_rain.append(i)
				ans.append(1)
			else:
				lake = rains[i]
				ans.append(-1)
				if lake not in last_rained.keys():
					last_rained[lake] = i
				else:
					lr = last_rained[lake]
					zl = len(no_rain)
					if len(no_rain) == 0 or no_rain[zl - 1] < lr:
						return []
					else:
						empty = self.find_min_greater(no_rain, lr)
						ans[no_rain[empty]] = lake
						last_rained[lake] = i
						no_rain.pop(empty)
		return ans


from collections import deque

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		dry_sequence = [1 for _ in range(len(rains))]
		full_lakes = {}
		dry_days = deque()
		for (i, lake) in enumerate(rains):
			if lake:
				dry_sequence[i] = -1
				if lake in full_lakes:
					if dry_days:
						index = 0
						while index < len(dry_days) and dry_days[index] <= full_lakes[lake]:
							index += 1
						if index < len(dry_days):
							dry_sequence[dry_days[index]] = lake
							del dry_days[index]
						else:
							return []
					else:
						return []
				full_lakes[lake] = i
			else:
				dry_days.append(i)
		return dry_sequence


from collections import defaultdict

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		dry_days = []
		filled_lakes = {}
		ans = [1] * len(rains)
		for i in range(len(rains)):
			if rains[i] != 0:
				ans[i] = -1
			if rains[i] in filled_lakes:
				if not dry_days:
					return []
				else:
					day_to_dry_lake = bisect.bisect_left(dry_days, filled_lakes[rains[i]])
					if day_to_dry_lake >= len(dry_days):
						return []
					ans[dry_days[day_to_dry_lake]] = rains[i]
					dry_days.pop(day_to_dry_lake)
					filled_lakes.pop(rains[i], None)
			if rains[i] == 0:
				dry_days.append(i)
			else:
				filled_lakes[rains[i]] = i
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		availables = []
		n = len(rains)
		ans = [-1] * n
		prev_rain = dict()
		for day in range(n):
			if rains[day] == 0:
				availables.append(day)
			else:
				lake = rains[day]
				if lake not in prev_rain:
					prev_rain[lake] = day
				else:
					if len(availables) == 0 or availables[-1] < prev_rain[lake]:
						return []
					low = 0
					high = len(availables) - 1
					while low < high:
						med = (low + high) // 2
						if availables[med] < prev_rain[lake]:
							low = med + 1
						else:
							high = med
					chosen_day = availables[low]
					availables.remove(chosen_day)
					prev_rain[lake] = day
					ans[chosen_day] = lake
		while availables:
			ans[availables[-1]] = 20
			availables.pop()
		return ans


from collections import defaultdict

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lake = defaultdict(list)
		ans = [1] * len(rains)
		for i in range(len(rains)):
			rain = rains[i]
			if rain == 0:
				lake[0].append(i)
			else:
				ans[i] = -1
				if len(lake[0]) == 0 and len(lake[rain]) != 0:
					return []
				elif len(lake[0]) != 0 and len(lake[rain]) != 0:
					for k in lake[0]:
						if k > lake[rain][0]:
							ans[k] = rain
							lake[0].remove(k)
							lake[rain] = [i]
							break
					else:
						return []
				elif len(lake[rain]) == 0:
					lake[rain].append(i)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		sol = [53456 for _ in range(len(rains))]
		pos = collections.defaultdict(list)
		for (idx, n) in enumerate(rains):
			if n > 0:
				pos[n].append(idx)
		for key in pos:
			pos[key].reverse()
		q = []
		used = set()
		for (idx, n) in enumerate(rains):
			if n > 0:
				if n in used:
					return []
				else:
					pos[n].pop()
					if pos[n]:
						heapq.heappush(q, (pos[n][-1], n))
					else:
						heapq.heappush(q, (math.inf, n))
					used.add(n)
				sol[idx] = -1
			elif n == 0:
				if q:
					(_, val) = heapq.heappop(q)
					sol[idx] = val
					used.remove(val)
		return sol


from queue import PriorityQueue

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		pq = PriorityQueue()
		rainOnLake = {}
		for (i, v) in enumerate(rains):
			if v > 0:
				if v not in rainOnLake:
					rainOnLake[v] = []
				rainOnLake[v].append(i)
		lakes = {}
		ans = [-1] * len(rains)
		for (i, v) in enumerate(rains):
			if v > 0:
				if lakes.get(v, 0) > 0:
					return []
				lakes[v] = 1
				rainSched = rainOnLake[v]
				rainSched.pop(0)
				if rainSched:
					nextRain = rainSched[0]
					pq.put((nextRain, v))
			elif v == 0:
				if pq.qsize() <= 0:
					ans[i] = 111111111
				else:
					(d, l) = pq.get()
					ans[i] = l
					lakes[l] = 0
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ret = [1] * len(rains)
		filled = dict()
		dryDays = list()
		for (ind, rain) in enumerate(rains):
			if rain > 0:
				ret[ind] = -1
				if rain not in filled:
					ret[ind] = -1
					filled[rain] = ind
					continue
				else:
					if not dryDays:
						return []
					found = False
					print(ind)
					for day in dryDays:
						if day > filled[rain]:
							ret[day] = rain
							dryDays.remove(day)
							found = True
							filled[rain] = ind
							break
					if not found:
						return []
			else:
				dryDays.append(ind)
		return ret


from bisect import bisect, bisect_left
from typing import List

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		result = []
		filled = {}
		free_day = []
		for (index, city) in enumerate(rains):
			if city:
				result.append(-1)
				if city not in filled:
					filled[city] = index
				else:
					if len(free_day) > 0 and free_day[-1] > filled[city]:
						dry_day = bisect_left(free_day, filled[city])
						result[free_day.pop(dry_day)] = city
						filled[city] = index
						pass
					else:
						return []
					pass
				pass
			else:
				result.append(1)
				free_day.append(index)
				pass
			pass
		return result


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		last_ids = {}
		next_ids = [0] * len(rains)
		for i in reversed(range(len(rains))):
			if rains[i] > 0:
				if rains[i] in last_ids:
					next_ids[i] = last_ids[rains[i]]
				last_ids[rains[i]] = i
		prio = []
		result = [-1] * len(rains)
		for i in range(len(rains)):
			if rains[i] > 0:
				if len(prio) > 0 and prio[0] <= i:
					return []
				if next_ids[i] > 0:
					heapq.heappush(prio, next_ids[i])
			elif len(prio) > 0:
				result[i] = rains[heapq.heappop(prio)]
			else:
				result[i] = 1
		return result


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		free_days = []
		lake_tracker = {}
		free_days_balance = 0
		ans = [-1 if rains[i] > 0 else 1 for i in range(len(rains))]
		for i in range(len(rains)):
			if rains[i] > 0:
				lake = rains[i]
				if lake in lake_tracker:
					if free_days_balance > 0:
						index = lake_tracker[lake]
						fnd = None
						for free_day in free_days:
							if index < free_day:
								fnd = free_day
								break
						if not fnd:
							return []
						free_days_balance = free_days_balance - 1
						lake_tracker[lake] = i
						ans[fnd] = lake
						free_days.remove(fnd)
					else:
						return []
				else:
					lake_tracker[lake] = i
			else:
				free_days_balance = free_days_balance + 1
				free_days.append(i)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		op = []
		lakes = dict()
		days = []
		for (i, r) in enumerate(rains):
			if r > 0:
				op.append(-1)
				if r in lakes.keys():
					day = lakes[r]
					v = -1
					for d in days:
						if d > day:
							v = d
							break
					if v > 0:
						days.remove(v)
						op[v] = r
					else:
						return []
				lakes[r] = i
			else:
				op.append(99999)
				days.append(i)
		return op


class Solution(object):

	def avoidFlood(self, rains):
		aux = dict()
		for i in range(len(rains)):
			if rains[i] not in aux:
				aux[rains[i]] = deque()
			aux[rains[i]].append(i)
		q = []
		ans = [1] * len(rains)
		for i in range(len(rains)):
			if rains[i] == 0:
				if q:
					(index, val) = heapq.heappop(q)
					if index < i:
						return []
					else:
						ans[i] = val
			else:
				ans[i] = -1
				if len(aux[rains[i]]) > 1:
					aux[rains[i]].popleft()
					heapq.heappush(q, (aux[rains[i]][0], rains[i]))
		if len(q):
			return []
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		ans = []
		lakes = {}
		freeDays = []
		for i in range(0, len(rains)):
			if rains[i] != 0:
				if rains[i] not in lakes:
					lakes[rains[i]] = []
					lakes[rains[i]].append(0)
					lakes[rains[i]].append(i)
				elif lakes[rains[i]][0] == 1 and len(freeDays) > 0:
					for j in range(0, len(freeDays)):
						if freeDays[j] > lakes[rains[i]][1]:
							ans[freeDays[j]] = rains[i]
							lakes[rains[i]][0] -= 1
							lakes[rains[i]][1] = i
							freeDays.pop(j)
							break
				lakes[rains[i]][0] += 1
				lakes[rains[i]][1] = i
				if lakes[rains[i]][0] > 1:
					return []
				ans.append(-1)
			else:
				freeDays.append(i)
				ans.append(1)
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = collections.defaultdict(bool)
		lastrain = collections.defaultdict(int)
		res = []
		dry = []
		for (k, v) in enumerate(rains):
			if v > 0:
				if not lakes[v]:
					lakes[v] = True
					res.append(-1)
					lastrain[v] = k
				elif dry == []:
					return []
				else:
					i = 0
					found = False
					while i < len(dry) and (not found):
						if dry[i] > lastrain[v]:
							found = True
							dry_day = dry[i]
						else:
							i += 1
					if found:
						res[dry_day] = v
						lastrain[v] = k
						dry.pop(i)
						res.append(-1)
					else:
						return []
			elif v == 0:
				res.append(1)
				dry.append(k)
		return res


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		lakes = {}
		zeroes = []
		length = len(rains)
		for (i, rain) in enumerate(rains):
			if rain == 0:
				zeroes.append(i)
				continue
			if rain in lakes:
				lake_index = lakes[rain]
				found = False
				for (j, zero) in enumerate(zeroes):
					if zero > lake_index:
						rains[zero] = rain
						found = True
						del zeroes[j]
						break
				if not found:
					return []
				lakes[rain] = i
				rains[i] = -1
			else:
				lakes[rain] = i
				rains[i] = -1
		for zero in zeroes:
			rains[zero] = 1
		return rains


import bisect

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		dry_days = []
		last_rainy_day = {}
		ans = [-1 if rain > 0 else 1 for rain in rains]
		for (i, rain) in enumerate(rains):
			if not rain:
				dry_days.append(i)
			elif rain not in last_rainy_day:
				last_rainy_day[rain] = i
			elif not dry_days:
				return []
			else:
				index = bisect.bisect_left(dry_days, last_rainy_day[rain])
				if index >= len(dry_days):
					return []
				ans[dry_days.pop(index)] = rain
				last_rainy_day[rain] = i
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		nex = [-1] * len(rains)
		last = {}
		for (i, n) in enumerate(rains):
			if n in last:
				nex[last[n]] = i
			last[n] = i
		(prio, answer) = ([], [])
		for (i, event) in enumerate(rains):
			if prio and prio[0] <= i:
				return []
			if event != 0:
				if nex[i] != -1:
					heapq.heappush(prio, nex[i])
				answer.append(-1)
			else:
				answer.append(rains[heapq.heappop(prio)] if prio else 1)
		return answer


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		full_lakes = {}
		sunny_days = []
		res = []
		for (i, rain) in enumerate(rains):
			if rain == 0:
				res.append(1)
				sunny_days.append(i)
			else:
				if rain in full_lakes:
					last_rain = full_lakes[rain]
					earliest_sunny_day = -1
					for day in sunny_days:
						if day > last_rain and day < i:
							earliest_sunny_day = day
							sunny_days.remove(day)
							break
					if earliest_sunny_day == -1:
						return []
					res[earliest_sunny_day] = rain
					res.append(-1)
				else:
					res.append(-1)
				full_lakes[rain] = i
		return res


import sortedcontainers

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		n = len(rains)
		ans = [-1] * n
		track = {}
		ptr = 0
		dries = sortedcontainers.SortedList()
		while ptr < n:
			lake = rains[ptr]
			if lake > 0:
				if lake in track:
					last_rain = track[lake]
					if not dries:
						return []
					idx = dries.bisect_right(last_rain)
					if idx >= len(dries):
						return []
					dry_pos = dries[idx]
					if dry_pos < last_rain:
						return []
					dries.discard(dry_pos)
					ans[dry_pos] = lake
					track[lake] = ptr
				else:
					track[lake] = ptr
			else:
				dries.add(ptr)
			ptr += 1
		for i in dries:
			ans[i] = 1
		return ans


from heapq import heappush, heappop

class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		appears = dict()
		for i in range(len(rains)):
			if not rains[i]:
				continue
			if not rains[i] in appears:
				appears[rains[i]] = []
			appears[rains[i]].append(i)
		next_rain = dict()
		for v in appears.values():
			for i in range(len(v) - 1):
				next_rain[v[i]] = v[i + 1]
		h = []
		ans = [-1] * len(rains)
		for i in range(len(rains)):
			if rains[i]:
				if i in next_rain:
					heappush(h, (next_rain[i], rains[i]))
			elif h:
				(day, idx) = heappop(h)
				if day < i:
					return []
				else:
					ans[i] = idx
			else:
				ans[i] = 1
		if h:
			return []
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		zeros = []
		last = {}
		ans = [-1] * len(rains)
		for i in range(len(rains)):
			if rains[i] == 0:
				ans[i] = 1
		for (i, lake) in enumerate(rains):
			if lake == 0:
				zeros.append(i)
			elif lake in last:
				prev_idx = last[lake]
				zero = bisect_left(zeros, prev_idx)
				if zero < len(zeros):
					zero_lake = zeros.pop(zero)
					last[lake] = i
					ans[zero_lake] = lake
				else:
					return []
			else:
				last[lake] = i
		return ans


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		counter = collections.Counter()
		firstSeen = {}
		empty = [-1] * len(rains)
		sunny = {}
		for (day, lake) in enumerate(rains):
			if lake > 0:
				if counter[lake] >= 1:
					for index in sunny:
						if index > firstSeen[lake]:
							empty[index] = lake
							counter[lake] -= 1
							del sunny[index]
							break
					if counter[lake] >= 1:
						return []
				counter[lake] += 1
				firstSeen[lake] = day
			else:
				sunny[day] = 1
		for day in sunny:
			empty[day] = 1
		return empty


class Solution:

	def avoidFlood(self, rains: List[int]) -> List[int]:
		closest = []
		locs = collections.defaultdict(collections.deque)
		for (i, lake) in enumerate(rains):
			locs[lake].append(i)
		ret = []
		for (i, lake) in enumerate(rains):
			if closest and closest[0] == i:
				return []
			if not lake:
				if not closest:
					ret.append(1)
					continue
				nxt = heapq.heappop(closest)
				ret.append(rains[nxt])
			else:
				l = locs[lake]
				l.popleft()
				if l:
					nxt = l[0]
					heapq.heappush(closest, nxt)
				ret.append(-1)
		return ret