<p>You are given an array <code>nums</code> consisting of <strong>non-negative</strong> integers.</p>

<p>We define the score of subarray <code>nums[l..r]</code> such that <code>l &lt;= r</code> as <code>nums[l] AND nums[l + 1] AND ... AND nums[r]</code> where <strong>AND</strong> is the bitwise <code>AND</code> operation.</p>

<p>Consider splitting the array into one or more subarrays such that the following conditions are satisfied:</p>

<ul>
	<li><strong>E</strong><strong>ach</strong> element of the array belongs to <strong>exactly</strong> one subarray.</li>
	<li>The sum of scores of the subarrays is the <strong>minimum</strong> possible.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of subarrays in a split that satisfies the conditions above.</em></p>

<p>A <strong>subarray</strong> is a contiguous part of an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,2,0,1,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can split the array into the following subarrays:
- [1,0]. The score of this subarray is 1 AND 0 = 0.
- [2,0]. The score of this subarray is 2 AND 0 = 0.
- [1,2]. The score of this subarray is 1 AND 2 = 0.
The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,7,1,3]
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        # First, we have x AND y <= x (or y).
        # The minimum possible scores of subarrays is AND of all the numbers in nums.
        # Proof: Given an array and any partition to two parts. The AND sums of two parts are X and Y respectively. SO the sum of scores is X + Y. However, if we choose to have only one subarray, the score is X AND Y. We have X AND Y <= X <= X + Y.
        # When the minimum score is known, we want to find a partition such that:
        # (x1 & x2 &...) + (y1 & y2 & ...) + ... = (x1 & x2 & ... & y1 & y2 & ...) = M.
        # Each part has (x1 & x2 & ...) >= M and M >= 0.
        # 1. If M > 0, then the partition can only be 1. If partition number is K > 1, then the left >= KM > M, contradiction.
        # 2. If M == 0, then we can have multiple partitions. We want to find the smallest prefix such that AND sum is 0, and so on.
        min_sum = -1
        for num in nums:
            min_sum &= num
        if min_sum > 0:
            return 1
        else:
            ans = 0
            cur = -1
            for num in nums:
                cur &= num
                if cur == 0:
                    ans += 1
                    cur = -1
            return ans
721