We are given hours, a list of the number of hours worked per day for a given employee.
A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.
A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.
Return the length of the longest well-performing interval.
 
Example 1:
Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

 
Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

Difficulty: interview

Starter code:

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        

Solutions:
class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans, count, seen = 0, 0, {}
        for i, hour in enumerate(hours):
            count = count + 1 if hour > 8 else count - 1
            if count > 0:
                ans = i + 1
            else:
                if count not in seen:
                    seen[count] = i
                if count - 1 in seen:
                    ans = max(ans, i - seen[count - 1])
        return ans

        


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans, cum, seen = 0, 0, {}
        for i, hour in enumerate(hours):
            cum = cum + 1 if hour > 8 else cum - 1
            if cum > 0:
                ans = i + 1
            else:
                if cum not in seen:
                    seen[cum] = i
                if cum - 1 in seen:
                    ans = max(ans, i - seen[cum - 1])
        return ans

class Solution:
    def findslavedays(self,hours):
        a=0
        b=0
        slave=0
        nonslave=0
        slavedays=0
        while b<len(hours):
          #  print(a,b,slave,nonslave,slavedays)
            if slave>nonslave:
                slavedays=max(slavedays,b-a+slave-nonslave-1)
            if a==b:
                if hours[a]<=8:
                    nonslave+=1
                else:
                    slave+=1
                b+=1
                continue
            if slave<nonslave:
                if hours[a]<=8:
                    nonslave-=1
                else:
                    slave-=1
                a+=1
            elif slave>=nonslave:
                if hours[b]<=8:
                    nonslave+=1
                else:
                    slave+=1
                b+=1
            
            if slave>nonslave:
                slavedays=max(slavedays,b-a+slave-nonslave-1)
        print(a,b)
        while a>0:
            a-=1
            if hours[a]<=8:
                nonslave+=1
            else:
                slave+=1
            if slave>nonslave:
                slavedays=max(slavedays,b-a+slave-nonslave-1)
        if slave>nonslave:
                slavedays=max(slavedays,b-a+slave-nonslave-1)        
        return slavedays
    def longestWPI(self, hours: List[int]) -> int:
        isslave=[-1]*len(hours)
        sumslave=0
        for i in range(len(isslave)):
            if hours[i]>8:
                isslave[i]=1
        dic={}
        maxslavedays=0
        print(isslave)
        for i in range(len(isslave)):
            
            sumslave=isslave[i]+sumslave
          #  print(sumslave)
            if sumslave>0:
                maxslavedays=max(maxslavedays,i+1)

            if sumslave not in dic:
                dic[sumslave]=i
            if sumslave-1 in dic:
                
                maxslavedays=max(maxslavedays,i-dic[sumslave-1])
        print(dic)
        return maxslavedays
    
        print(isslave,sumslave)
        a=-1
        b=0
        dic={}
        dic[0]=-1
        for i in range(len(isslave)):
            
            if sumslave[i]>0:
                b=i
                maxslavedays=max(maxslavedays,b-a)
            if sumslave[i]<=0:
                a=i
        return maxslavedays
            
        #for i in range(1,len(isslave)):
            
        return 0
        slavelength1=self.findslavedays(hours)
        slavelength2=self.findslavedays(hours[::-1])
        return max(slavelength1,slavelength2)

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        score=0
        dic={}
        result=0
        for i,hour in enumerate(hours):
            if hour >8:
                score +=1
            else:
                score -=1

            if score>0:
                result = i+1
                
            if score not in dic:
                dic[score] = i
                
            
            if score-1 in dic:
                result=max(result, i -dic[score-1])
        return result    
    


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        res = score = 0
        seen = {}
        for i in range(len(hours)):
            h = hours[i]
            score = score + 1 if h > 8 else score - 1
            if score > 0:
                res = i + 1
            seen.setdefault(score, i)
            if score - 1 in seen:
                res = max(res, i - seen[score - 1])
        return res

import bisect

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        r, l, l_idx = [], [], []
        d = []
        for i, x in enumerate(hours):
            if i == 0:
                if x > 8:
                    d.append(1)
                else:
                    d.append(-1)
            else:
                if x > 8:
                    d.append(d[-1] + 1)
                else:
                    d.append(d[-1] - 1)
                    
        for i, x in enumerate(d):
            while len(r) > 0 and r[-1][0] <= x:
                r.pop()
            r.append((x, i))
            if len(l) == 0 or x < l[-1]:
                l.append(x)
                l_idx.append(i)
        
        ans = 0
        l.reverse()
        l_idx.reverse()
        
        for x in r:
            if x[0] > 0:
                ans = max(ans, x[1] + 1)
            else:
                idx = bisect.bisect_right(l, x[0] - 1)
                if idx >= 1:
                    ans = max(ans, x[1] - l_idx[idx - 1])
        
        return ans
        


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        nums = []
        for hour in hours:
            if hour > 8:
                nums.append(1)
            else:
                nums.append(-1)
        prevsum, sumv = [], 0
        for num in nums:
            sumv += num
            prevsum.append(sumv)
        stack = []
        prevsum = [0] + prevsum
        for i, val in enumerate(prevsum):
            if not stack or prevsum[stack[-1]] > val:
                stack.append(i)
        i, res = len(prevsum) - 1, 0
        while i >= 0:
            while stack and prevsum[stack[-1]] < prevsum[i]:
                res = max(res, i - stack[-1])
                stack.pop()
            i -= 1
        return res


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        d = {}
        d[0] = -1
        
        res = 0
        
        for i in range(len(hours)):
            hours[i] = (1 if hours[i] > 8 else -1) + (0 if i == 0 else hours[i-1])
            
            if hours[i] not in d:
                d[hours[i]] = i
            
            if hours[i] > 0:
                res = i+1
                
            target = hours[i] - 1
            
            if target in d:
                res = max(res, i - d[target])
        
        print(hours)
        print(d)
        return res
            
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        hours = [1 if i > 8 else -1 for i in hours]
        hsh = {}
        vals = [0 for i in hours]
        sm = 0
        for i in range(len(hours)-1, -1, -1):
            sm += hours[i]
            if sm > 0:
                vals[i] = max(vals[i], len(hours) - i)
            hours[i] = sm
            smo = hours[i] - 1
            if smo in hsh:
                v = hsh[smo]
                vals[i] = max(vals[i], v - i + vals[v])
                
            if hours[i] not in hsh:
                hsh[hours[i]] = i
        
        return max(vals)
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        d = {}
        P = [0] #prefix sum
        F = [0 for i in range(len(hours))]
        res = 0
        for i in range(len(hours)):
            P.append(P[-1] + (1 if hours[i] > 8 else -1))
            if P[-1] > 0:
                F[i] = i + 1
            else:
                s = d.get(P[-1] - 1, -1)
                if s >= 0:
                    F[i] = max(F[i], i - s + F[s])
            if P[-1] not in d:
                d[P[-1]] = i
            res = max(res, F[i])   

        return res

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        val = 0
        result = 0
        table = dict()
        for i in range(len(hours)):
            hour = hours[i]
            if hour > 8:
                val += 1
            else:
                val -= 1
                
            if val > 0:
                result = i + 1
            else:
                if val not in table:
                    table[val] = i
                if val - 1 in table:
                    dist = i - table[val - 1]
                    if dist > result:
                        result = dist
        
        return result

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        sum=0
        ans=0
        d={}
        for i in range(len(hours)):
            sum=sum+1 if hours[i] >8 else sum-1
            if sum>0:
                ans=i+1
            else:
                if sum not in d:
                    d[sum]=i
                if sum-1 in d:
                    ans=max(ans,i-d[sum-1])
        return ans
        
            
                


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        seen = {}
        result,score = 0,0
        for i,num in enumerate(hours):
            score += 1 if num > 8 else -1
            if score > 0:
                result = i+1
            elif score -1 in seen:
                result = max(result, i - seen[score -1])
            seen.setdefault(score, i)
        return result
            
                


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        
        n = len(hours)
        hashmap = dict()
        total=0
        res=0

        for i in range(n):
            if hours[i]<=8:
                total-=1
            else:
                total+=1

            if total>0:
                res=i+1
                continue
            else:
                if total not in hashmap:
                    hashmap[total] = i
                if (total-1) in hashmap:
                    res = max(res, i-hashmap[total-1])
        return res
        
        
            
            
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        # Convert array to 0 and 1s
        bits = [1 if x > 8 else -1 for x in hours]
        # Problem becomes: find the longest interval bits[i:j] where sum(bits[i:j]) > 0
        # Get prefix sum of bits
        pref = [0] * (len(bits)+1)
        for i in range(1, len(bits)+1):
            pref[i] = pref[i-1] + bits[i-1]
        # Problem becomes: find the longest interval pref[i:j] where pref[j] > pref[i]
        # Sort index of pref by value. Problem becomes: find the largest sorted_pref[j]-sorted_pref[i] where j > i
        # Greedy to solve the new problem
        ans = 0
        min_val = len(bits) + 1
        for y in sorted(enumerate(pref), key=lambda x: (x[1], -x[0])):
            min_val = min(min_val, y[0])
            ans = max(ans, y[0] - min_val)
        return ans


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        res = score = 0
        seen = {}
        for i, h in enumerate(hours):
            score = score + 1 if h > 8 else score - 1
            if score > 0:
                res = i + 1
            seen.setdefault(score, i)
            if score - 1 in seen:
                res = max(res, i - seen[score - 1])
        return res


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        
        s = 0
        seen = {}
        ans = 0
        
        for i,h in enumerate(hours):
            if h > 8:
                s += 1
            else:
                s -= 1
                
            if s > 0:
                ans = i+1
            
            seen.setdefault(s, i)
            
            if s-1 in seen:
                ans = max(ans, i-seen[s-1])
        
        return ans
                
        



class Solution:
    def longestWPI(self, hours):
        
        res = score = 0
        seen = {}
        
        for i, h in enumerate(hours):
            print((i,h))
            
            if h > 8: score += 1
            else: score -= 1
                
            if score > 0:
                res = i + 1
            seen.setdefault(score, i)
            if score - 1 in seen:
                res = max(res, i - seen[score - 1])
        return res
    
    
#tiring_count = 1, not_tiring_count = 0, max_length = 1
#tiring_count = 2, not_tiring_count = 0, max_length = 2
#tiring_count = 2, not_tiring_count = 1, max_length = 3
#tiring_count = 2, not_tiring_count = 2, tiring_count = 0
#tiring_count = 0, nt = 3
#nt = 4
#tiring count += 1
                    


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        hours = [1 if i > 8 else -1 for i in hours]
        hsh = {hours[0]:0}
        for i in range(1, len(hours)):
            hours[i] += hours[i-1]
            hsh[hours[i]] = i
            
        vals = [i+1 if hours[i] > 0 else 0 for i in range(len(hours))]
        for i in range(len(hours)):
            sm = hours[i] + 1
            if sm in hsh:
                v = hsh[sm]
                vals[v] = max(vals[v], v-i+vals[i])
                        
        return max(vals)
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        final = 0
        score = 0
        stack = {}
        for i in range(len(hours)):
            if hours[i] > 8 :
                score += 1
            else: 
                score -= 1
            stack.setdefault(score,i)
            if score > 0:
                final = i + 1
            if score - 1 in stack:
                final = max(final, i - stack[score-1])
        return final
                


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        L = [1 if i > 8 else -1 for i in hours]
        K = [1 if i > 8 else -1 for i in hours]
        mp = {}
        for i in range(0, len(hours)):
            if i > 0:
                s = L[i] = L[i] + L[i - 1]
            else:
                s = L[i]
            if s not in mp:
                mp[s] = {i: True}
            else:
                mp[s][i] = True
        
        #print(K)
        #print(L)
        result = 0
        for i, c in enumerate(L):
            if L[-1] > L[i]:
                result = max(result, len(K) - i - 1)
                #print(\"ss\", i, result)
            if 0 < L[i]:
                result = max(result, i + 1) 
                #print(\"ddd\", i)
                
            if i > 0 and L[i - 1] + 1 in mp:
                s = mp[L[i - 1] + 1]
                #print(result, s, i)
                result = max(result, max(s) - i + 1)
                #result = max(result, i + 1 - min(s))
            if L[i] - 1 in mp:
                s = mp[L[i] - 1]
                #print(result, s, i)
                # result = max(result, max(s) - i + 1)
                result = max(result, i - min(s))
            #print(result, i)
        return result

    
    def longestWPI(self, hours: List[int]) -> int:
        mp = {}
        accu = 0
        result = 0
        for i, v in enumerate(hours):
            accu += 1 if v > 8 else -1
            # print(accu)
            if accu > 0:
                result = max(result, i + 1)
                print((result, i))
            if accu - 1 in mp:
                result = max(result, i - mp[accu-1])
                print((result, i))
            if accu not in mp:
                mp[accu] = i
        return result
                


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ret = 0
        overall = 0

        totals = {}
        for i, h in enumerate(hours):
            if h > 8:
                overall += 1 
            else:
                overall -= 1
            
            if overall > 0:
                ret = i + 1
            else:
                if overall-1 in totals:
                    length = i - totals[overall-1]
                    ret = max(ret, length)
                if overall not in totals:
                    totals[overall] = i
    
        return ret

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        pre_sum = [0]
        for i, v in enumerate(hours):
            hours[i] = 1 if v > 8 else -1
            pre_sum.append(pre_sum[-1] + hours[i])

        dec_stack = [] # idx to pre_sum
        for i, v in enumerate(pre_sum):
            if len(dec_stack) == 0 or (len(dec_stack) > 0 and v < pre_sum[dec_stack[-1]]):
                dec_stack.append(i)
        max_r = -math.inf
        max_width = 0
        for r in range(len(pre_sum)-1, -1, -1):
            n = pre_sum[r]
            if n < max_r:
                continue
            max_r = n
            while len(dec_stack) > 0:
                # pop top < n
                left_idx = dec_stack[-1]
                if pre_sum[left_idx] < n:
                    dec_stack = dec_stack[0:-1]
                    max_width = max(max_width, r - left_idx)
                else:
                    break
            if len(dec_stack) == 0:
                break
        return max_width

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        hours = [1 if h > 8 else -1 for h in hours]
            
        down = {1: 0}
        s = 0
        ans = 0
        for i,h in enumerate(hours):
            if h < 0:
                if s not in down:
                    down[s] = i
            s += h
            if s in down:
                ans = max(ans, i - down[s])
            if s > 0:
                ans = max(ans, i+1)
        return ans


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        days = [1 if hour > 8 else -1 for hour in hours] #find longest strictly positive subarr
        prefSums = days[:]
        for i in range(1, len(hours)):
            prefSums[i] = days[i] + prefSums[i - 1]
        result = 0
        prefixLookup = {}
        for i in range(len(hours)):
            sumToHere = prefSums[i] #longest answer ending here 
            if sumToHere >= 1:
                result = max(result, i + 1)
            else:
                earlierPrefSumNeeded = sumToHere - 1
                if earlierPrefSumNeeded in prefixLookup:
                    result = max(result, i - prefixLookup[earlierPrefSumNeeded])
            if sumToHere not in prefixLookup:
                prefixLookup[sumToHere] = i
        return result


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        lt = []
        for hour in hours:
            if hour > 8:
                lt.append(1)
            else:
                lt.append(-1)
        seen = {}
        s = 0
        mx = 0
        for idx, ele in enumerate(lt):
            s += ele
            print((s, idx, mx))
            if s > 0 : #atleast more 9
                mx = max(mx, (idx+1))
            else:    
                if (s-1) in seen:
                    i = seen[s-1]
                    mx = max(mx, idx-i)
            if (s) not in seen:
                seen[s] = idx
        return mx        
        
                
        


# [9,9,6,0,6,6,9]

# [1,1,-1,-1,-1,1]
#  1 2  1  0  -1 0
# [1,1,-1,-1,-1,1, 1]
class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        prefix = []
        for hour in hours:
            if hour > 8:
                prefix.append(1)
            else:
                prefix.append(-1)
                
        curr_sum = 0
        seen = {0:-1}
        res = 0
        
        for i, num in enumerate(prefix):
            curr_sum += num
            if curr_sum > 0:
                res = i + 1
                
            if curr_sum - 1 in seen:
                res = max(res, i - seen[curr_sum - 1])
            
            if curr_sum not in seen:
                seen[curr_sum] = i
        
        return res
    
        


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        cur = res = 0
        seen = {}
        for i, h in enumerate(hours):
            cur += 1 if h > 8 else -1
            if cur > 0: res = max(res, i + 1)
            else:
                if cur - 1 in seen:
                    res = max(res, i - seen[cur - 1])
            if cur not in seen:
                seen[cur] = i
        
        return res


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        hours = [1 if x > 8 else -1 for x in hours]
        s = 0
        idx = {}
        ans = 0
        for i in range(len(hours)):
            s += hours[i]
            if s > 0:
                ans = i + 1
            if s not in idx:
                idx[s] = i
            if (s - 1) in idx:
                ans = max(ans, i - idx[s - 1])
        return ans

#https://leetcode.com/problems/longest-well-performing-interval/discuss/334565/JavaC%2B%2BPython-O(N)-Solution-Life-needs-996-and-669
    
class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        seen = dict()
        cnt = 0
        res = 0
        for idx, h in enumerate(hours):
            if h>8:
                cnt += 1
            else:
                cnt -= 1
            if cnt>0:
                res = idx+1
            else:
                if cnt-1 in seen:
                    res = max(res, idx-seen[cnt-1])
            if cnt not in seen:
                seen[cnt] = idx
        return res


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        Sum, ans = 0, 0
        cache = {}
        for i, n in enumerate(hours):
            Sum = Sum + 1 if n > 8 else Sum - 1
            if Sum > 0: ans = i + 1
            if Sum-1 in cache:
                ans = max(ans, i - cache[Sum-1])
            cache.setdefault(Sum, i)
        return ans


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        hours = [1 if h > 8 else -1 for h in hours]
        seen = {}
        ans = cur = 0
        for i, h in enumerate(hours):
            cur += h
            seen.setdefault(cur, i)
            if cur > 0:
                ans = i + 1
            elif cur - 1 in seen:
                ans = max(ans, i - seen[cur - 1])
        return ans
        
        # hours = [1 if h > 8 else 0 for h in hours]
        # acc = [0] + list(accumulate(hours))
        # i, j = 0, len(hours) - 1
        # cur = sum(hours)
        # ans = 0
        # while i <= j:
        #     if cur > (j - i + 1) // 2:
        #         return j - i + 1
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        res = score = 0
        seen = {}
        for i, h in enumerate(hours):
            score = score + 1 if h > 8 else score - 1
            if score > 0:
                res = i + 1
            seen.setdefault(score, i)
            if score - 1 in seen:
                res = max(res, i - seen[score - 1])
        return res

class Solution:
    def longestWPI(self, h: List[int]) -> int:
        n=len(h)
        for i in range(n):
            if h[i]>8:
                h[i]=1
            else:
                h[i]=-1
        #longest subarray with sum >0
        pre=[0]*n 
        pre[0]=h[0]
        maxi=0
        for i in range(1,n):
            pre[i]=pre[i-1]+h[i]
        d={}
        print(pre)
        for x in range(n):
            if pre[x]>0:
                maxi=x+1
            if d.get(pre[x]-1,-1)!=-1:
                #print(i,d[pre[x]])
                maxi=max(maxi,x-d[pre[x]-1])
            if d.get(pre[x],-1)==-1:
                d[pre[x]]=x
        return maxi

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        i=0
        prefixSum=0
        existed={0:0}
        res=0
        while i<=len(hours)-1:
            if hours[i]>=9:
                prefixSum+=1
            else:
                prefixSum-=1
            
            if prefixSum not in existed:
                existed[prefixSum]=i+1
            if prefixSum-1 in existed:
                res=max(res, i+1-existed[prefixSum-1])
            if prefixSum>=1:
                res=max(res, i+1)
            i+=1
        #print(existed)
        return res

class Solution:
    # Use an index to store where
    #       score - 1            score
    # |-----------|----------------|
    #             |--------1-------|
    def longestWPI(self, hours: List[int]) -> int:
        score, longest = 0, 0
        index = {}
        for i, n in enumerate(hours):
            score += 1 if n > 8 else -1
            if score > 0:  # more tiring days so far
                longest = max(longest, i + 1)
            index.setdefault(score, i)  # record the earliest presum with score
            if score - 1 in index:
                longest = max(longest, i - index[score - 1])
        return longest

import bisect

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        
        starts = []
        startIndexes = []
        counts = [0] * len(hours)
        
        for i in range(len(hours)):
            if i > 0:
                counts[i] = counts[i - 1]
            if hours[i] > 8:
                counts[i] += 1
            else:
                counts[i] -= 1
                
        counts = [0] + counts
        
        for i in range(len(counts) - 1, -1 , -1):
            numGood = counts[i]
            while starts and starts[-1] >= numGood:
                starts.pop()
                startIndexes.pop()
                
            starts.append(numGood)
            startIndexes.append(i)
            
        maxLen = 0
        for i, c in enumerate(counts):
            target = c - 1 
            # pos1 = len(starts) - 1
            # while pos1 >= 0 and starts[pos1] > target:
            #     pos1 -= 1
            pos = bisect.bisect_right(starts, target)
            if pos == len(starts) or starts[pos] > target:
                pos -= 1
            if pos >= 0:
                lenHere = i - startIndexes[pos]
                maxLen = max(maxLen, lenHere)
                
        return maxLen
                
           
            
        


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        hoursLen = len(hours)
        tDay = []
        preSum = 0
        preSumDict = {0:-1}
        preSumKeys = [0]
        ans = 0
        
        def insertAt(x):
            l = 0
            r = len(preSumKeys)-1
            if x < preSumKeys[l]:
                return 0
            if x > preSumKeys[r]:
                return r + 1
            while r > l:
                m = (r + l)//2
                if preSumKeys[m] < x:
                    l = m + 1
                else:
                    r = m
            return l
        
        ans = 0
        for i, hour in enumerate(hours):
            if hour > 8:
                tDay.append(1)
                preSum += 1               
            else:
                tDay.append(-1)
                preSum -= 1  
            tempIndex = insertAt(preSum)
            if preSum not in preSumDict:
                preSumDict[preSum] = i
                preSumKeys.insert(tempIndex, preSum)
            if tempIndex > 0:
                preSumDict[preSumKeys[tempIndex]] = min( preSumDict[preSumKeys[tempIndex-1]], preSumDict[preSumKeys[tempIndex]])
                ans = max(ans, i - preSumDict[preSumKeys[tempIndex-1]])
        # print(preSumKeys)
        # print(preSum)
        return ans

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        s = 0
        maxLen = 0
        seen = {}
        for idx, hour in enumerate(hours):
            if hour > 8:
                s += 1
            else:
                s -=1
            if s > 0:
                res = idx + 1
                maxLen = max(maxLen, res)
            else:
                if (s-1) in seen:
                    res = (idx - seen[s-1])
                    maxLen = max(maxLen, res)
            
            if s not in seen:
                seen[s] = idx
        return maxLen         
                
            


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        stack,res,first=0,0,{}
        for day,i in enumerate(hours):
            stack=stack+1 if i>8 else stack-1
            first.setdefault(stack, day)
            if stack>0:res=day+1
            elif stack-1 in first:
                res=max(res,day-first[stack-1])
        return res

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        stack = []
        ans = accu = 0
        for i, h in enumerate(hours):
            if h > 8:
                accu += 1
            else:
                accu -= 1
            if accu > 0:
                ans = i + 1
            else:
                L, U = -1, len(stack)
                while L + 1 < U:
                    m = (L + U) // 2
                    if stack[m][1] < accu:
                        U = m
                    else:
                        L = m
                if U < len(stack):
                    ans = max(ans, i - stack[U][0])
            if not stack or stack[-1][1] > accu:
                stack.append((i, accu ))
        return ans


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        # ans, cum, seen = 0, 0, {}
        # for i, hour in enumerate(hours):
        #     cum = cum + 1 if hour > 8 else cum - 1
        #     if cum > 0:
        #         ans = i + 1
        #     else:
        #         if cum not in seen:
        #             seen[cum] = i
        #         if cum - 1 in seen:
        #             ans = max(ans, i - seen[cum - 1])
        # return ans
    
        res = score = 0
        seen = {}
        for i, h in enumerate(hours):
            score = score + 1 if h > 8 else score - 1
            if score > 0:
                res = i + 1
            seen.setdefault(score, i)
            if score - 1 in seen:
                res = max(res, i - seen[score - 1])
        return res

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        total = res = 0
        index = {}
        for i, h in enumerate(hours):
            total += 1 if h > 8 else -1
            if total > 0:
                res = i + 1
            if total - 1 in index:
                res = max(res, i - index[total-1])
            index.setdefault(total, i)
            
        return res
        
        


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        s = []
        for i in hours:
            if i > 8:
                s.append(1)
            else:
                s.append(-1)
                
        n = len(s)
        presum = [0]*(n+1)
        for i in range(1,(n+1)):
            presum[i] = presum[i-1] + s[i-1]
        
        stack = []
        n = len(presum)
        for i in range(n):
            if not stack or presum[stack[-1]] > presum[i]:
                stack.append(i)
        res = 0
        i = n-1
        while i > res:
            while stack and presum[stack[-1]] < presum[i]:
                res = max(res,i-stack[-1])
                stack.pop()
            i -=1
        return res

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        presum = 0
        res = 0
        mem = {}
        for i, h in enumerate(hours):
            presum += (1 if h > 8 else -1)
            if presum > 0:
                res = i + 1
            else:
                if presum - 1 in mem:
                    res = max(res, i - mem[presum - 1])
            if presum not in mem:
                mem[presum] = i
        return res