题目描述
给定一个长度为 NNN 的序列 {ai}\{a_i\}{ai}，序列中第 iii 个数字为 aia_iai，你可以对序列执行若干次操作，每次操作选定两个数字l,r(1≤l≤r≤n)l, r(1 \le l \le r \le n)l,r(1≤l≤r≤n)，使得∀i∈[l,r],ai=ai⨁al\forall i \in [l, r], a_i = a_i \bigoplus a_l∀i∈[l,r],ai=ai⨁al。题目要求操作的顺序按照 lll 严格单调递减的顺序进行操作。也就是说，假设一共执行了 TTT 次操作，第 iii 次操作选定的数字为 li,ril_i, r_ili,ri， 有 1≤lT<lT−1<⋯<l2<l1≤n1 \le l_T < l_{T - 1} < \cdots < l_2 < l_1 \le n1≤lT<lT−1<⋯<l2<l1≤n。求使得序列中的所有元素全部变成 000 所需的最少操作次数。
输入
第一行，一个正整数 N(1≤N≤106)N (1 \le N \le 10^6)N(1≤N≤106) 表示序列长度
第二行，NNN 个用空格隔开的正整数表示序列{ai}\{a_i\}{ai}, 第 iii 个正整数表示 ai(0≤ai≤106)a_i (0 \le a_i \le 10^6)ai(0≤ai≤106)
输出
一行一个整数表示最少操作次数。
样例输入 Copy
5
5 1 2 2 4
样例输出 Copy
4
提示
操作依次为：
1. [5,5][5, 5][5,5]，序列变为 5 1 2 2 0
2. [3,4][3, 4][3,4]，序列变为 5 1 0 0 0
3. [2,2][2, 2][2,2]，序列变为 5 0 0 0 0
4. [1,1][1, 1][1,1]，序列变为 0 0 0 0 0