# https://leetcode.com/problems/longest-square-streak-in-an-array
from typing import List

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        nums.sort()
        s = set()
        ret = 0
        for each in nums:
            if each in s:
                continue
            curr = each
            l = 1
            while curr * curr <= 10 ** 5:
                if self.search(nums, curr * curr):
                    curr *= curr
                    s.add(curr)
                    l += 1
                else:
                    break
            ret = max(l, ret)
        return ret if ret >= 2 else - 1

    def search(self, nums: List[int], num: int) -> bool:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == num:
                return True
            if nums[mid] < num:
                left = mid + 1
            else:
                right = mid - 1
        return False