#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n , k;
	cin >> n >> k;
	ll arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	vector<ll> v;
	ll sum = 0;
	for(int i = 1; i < n; i++){
		v.pb(abs(arr[i] - arr[i-1]));
		sum += v.back();
	}
	sort(all(v));
	for(int groups = 1; groups < k; groups++){
		sum -= v.back();
		v.pop_back();
	}
	cout << sum << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	int cur = arr[0];
	int part = 1;
	for(int i = 0; i < n; i++){
		cur &= arr[i];
		if(cur == 0){
			if(i == n-1)break;
			part++;
			cur = arr[i + 1];
		}
	}
	if(cur != 0)part--;
	part = max(part,1);
	cout << part << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

At the end of the array, you can only achieve xor of any subarray of the original array.

Now, we maintain a boolean array $$$b$$$ where $$$b_i$$$ is $$$1$$$ if there is some $$$j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$$$. Initially, $$$b$$$ is all $$$0$$$. We loop $$$j$$$ from $$$1$$$ to $$$n$$$ and check for each $$$k$$$ if $$$b_k=1$$$. If it is, then there is some position $$$p < j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$$$. If we take xor of range from $$$(p,j]$$$, then it will be $$$k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ (as $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p$$$ gets cancelled). This $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $$$n$$$ is large.

Time Complexity — $$$O(n \cdot 2^8)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &i : a)
            cin >> i;
 
        int const max_value = 1 << 8;
        vector<char> has_pref(max_value);
        has_pref[0] = true;
        int cur_xor = 0;
        int ans = 0;
        for (auto i : a) {
            cur_xor ^= i;
            for (int pref = 0; pref < max_value; ++pref) {
                if (has_pref[pref]) {
                    ans = max(ans, pref ^ cur_xor);
                }
            }
            has_pref[cur_xor] = true;
        }
 
        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define all(x) x.begin(),x.end()
 
void solve(){
	int n , m , q;
	cin >> n >> m >> q;
	string st;
	cin >> st;
	vector<pair<int,int>> ranges;
	for(int i = 0; i < m; i++){
		int l , r;
		cin >> l >> r;
		l--;
		r--;
		ranges.pb(mp(l,r));
	}
	set<int> s;
	for(int i = 0; i < n; i++)s.insert(i);
	vector<int> v;
	int pos_in_v[n];
	memset(pos_in_v,-1,sizeof pos_in_v);
	for(int i = 0; i < m; i++){
		auto it = s.lower_bound(ranges[i].vf);
		vector<int> toerase;
		while(it != s.end() && (*it) <= ranges[i].vs){
			toerase.pb((*it));
			v.pb(toerase.back());
			pos_in_v[toerase.back()] = v.size()-1;
			it++;
		}
		while(toerase.size()){
			s.erase(toerase.back());
			toerase.pop_back();
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(st[i] == '1')cnt++;
	}
	int ans = 0;
	for(int i = 0; i < min(cnt , (int)v.size()); i++){
		if(st[v[i]] == '0')ans++;
	}
	
	while(q--){
		int pos;
		cin >> pos;
		pos--;
		if(pos_in_v[pos] != -1 && pos_in_v[pos] < cnt){
			if(st[pos] == '0'){
				ans--;
			}
			else ans++;
		}
		if(st[pos] == '0'){
			st[pos] = '1';
			cnt++;
			if(cnt <= v.size() && st[v[cnt-1]] == '0')ans++;
		}
		else {
			st[pos] = '0';
			if(cnt > 0 && cnt <= v.size() && st[v[cnt-1]] == '0')ans--;
			cnt--;
		}
		cout << ans << '\n';
	}
}
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, ans[5005], holy[10][10][10];
map<vector<int>, int> GG;
int area(int x, int y, int z)
{
    int ok = max(x, max(y, z));
    int sum = x+y+z;
    if(2*ok >= sum) return 0;
    return sum*(sum-2*x)*(sum-2*y)*(sum-2*z);
}
int query(vector<int> v)
{
    sort(v.begin(), v.end());
    if(GG.find(v) != GG.end()) return GG[v];
    cout << "? " << v[0] << " " << v[1] << " " << v[2] << endl;
    int ret; cin >> ret; assert(ret != -1); return GG[v] = ret;
}
void print(bool found = true)
{
    if(!found)
    {
        cout << "! -1" << endl;
        exit(0);
    }
    cout << "! ";
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl; exit(0);
}
bool works()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            for(int k = j+1; k <= n; k++)
            {
                if(area(ans[i], ans[j], ans[k]) != holy[i][j][k])
                    return false;
            }
        }
    }
    return true;
}
void brute()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            for(int k = j+1; k <= n; k++)
                holy[i][j][k] = query({i, j, k});
        }
    }
    int mask = 1<<(2*n);
    int lol = 0;
    int workser = -1;
    for(int i = 0; i < mask; i++)
    {
        int copy = i;
        for(int k = 1; k <= n; k++)
        {
            ans[k] = 1+copy%4;
            copy/=4;
        }
        if(works())
        {
            workser = i;
            lol++;
        }
    }
    assert(lol);
    if(lol > 1) print(false);
    int copy = workser;
    for(int k = 1; k <= n; k++)
    {
        ans[k] = 1+copy%4;
        copy/=4;
    }
    print();
}

signed main()
{
    ios_base::sync_with_stdio(false); cin >> n;
    if(n <= 8) brute();
    map<int, int> nice;
    for(int i = 1; i <= 4; i++) nice[area(i, i, i)] = i;
    int a, b, X;
    
    {
        bool found = false;
        for(int i = 1; i <= min(n, 9) && !found; i++)
        {
            for(int j = i+1; j <= min(n, 9) && !found; j++)
            {
                for(int k = j+1; k <= min(n, 9) && !found; k++)
                {
                    if(nice[query({i, j, k})])
                    {
                        a = i;
                        b = j;
                        X = nice[query({i, j, k})];
                        found = true;
                    }
                }
            }
        }
    }
    if(X > 1)
    {
        map<int, int> ok;
        for(int i = 1; i <= 4; i++) ok[area(i, X, X)] = i;
        for(int i = 1; i <= n; i++) ans[i] = ((i==a) || (i==b))? X : ok[query({a, b, i})];
        print();
        return 0;
    }
    vector<int> non_ones;
    for(int i = 1; i <= n; i++)
    {
        if(i == a || i == b || query({i, a, b}))
            ans[i] = 1;
        else
            non_ones.push_back(i);
        if(non_ones.size() == 4) break;
    }
    if(non_ones.empty()) print();
    map<int, int> ok;
    for(int i = 2; i <= 4; i++) ok[area(1, i, i)] = i;
    int x, y, Z; x = y = -1; Z = 0;
    for(int i = 0; i < non_ones.size() && (Z == 0); i++)
    {
        for(int j = i+1; j < non_ones.size() && (Z == 0); j++)
        {
            if(ok[query({a, non_ones[i], non_ones[j]})])
            {
                x = non_ones[i];
                y = non_ones[j];
                Z = ok[query({a, non_ones[i], non_ones[j]})];
            }
        }
    }
    if(x == -1) print(false);
    map<int, int> fin; ans[x] = ans[y] = Z; 
    for(int i = 1; i <= 4; i++) fin[area(Z, Z, i)] = i;
    for(int i = 1; i <= n; i++) ans[i] = ans[i]? ans[i] : fin[query({x, y, i})];
    print();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5005;
int ans[N];
int n;
int dp[5][5][5];
int holy[11][11][11];
 
int area(int a, int b, int c){
    if (a >= b + c) return 0;
    if (b >= a + c) return 0;
    if (c >= a + b) return 0;
    
    int s = (a + b + c);
    return s * (s - 2 * a) * (s - 2 * b) * (s - 2 * c);
}
 
int query(int a, int b, int c){
    cout << "? " << a << " " << b << " " << c << endl;
    int ans; cin >> ans;
    return ans;
}
 
void print(bool found = true){
    if (!found){
        cout << "! -1\n";
        exit(0);
    } else {
        cout << "! ";
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << endl;
        exit(0);
    }
}
 
bool works(){
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            for (int k = j + 1; k <= n; k++){
                if (area(ans[i], ans[j], ans[k]) != holy[i][j][k])
                    return false;
            }
        }
    }
    
    return true;
}
 
void brutesmall(){
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            for (int k = j + 1; k <= n; k++){
                holy[i][j][k] = query(i, j, k);
            }
        }
    }
    
    int mask = 1 << (2 * n);
    int lol = 0;
    for (int i = 0; i < mask; i++){
        int copy = i;
        
        for (int i = 1; i <= n; i++){
            ans[i] = 1 + copy % 4;
            copy /= 4;
        }
        
        if (works()){
            lol++;
        }
    }
    
    if (lol > 1) print(false);
    
    for (int i = 0; i < mask; i++){
        int copy = i;
        
        for (int i = 1; i <= n; i++){
            ans[i] = 1 + copy % 4;
            copy /= 4;
        }
        
        if (works()){
            print();
        }
    }
}
 
void Solve() 
{
    cin >> n;
    
    for (int i = 1; i <= 4; i++){
        for (int j = 1; j <= 4; j++){
            for (int k = 1; k <= 4; k++){
                dp[i][j][k] = area(i, j, k);
            }
        }
    }
    
    if (n < 9){
        brutesmall();
    }
    
    vector <int> tuple(4, -1);
    while (true){
        if (tuple[0] != -1) break;
        int p1 = 1 + RNG() % n;
        int p2 = 1 + RNG() % n;
        int p3 = 1 + RNG() % n;
        
        if (p1 == p2 || p2 == p3 || p3 == p1) continue;
        int ar = query(p1, p2, p3);
        for (int j = 1; j <= 4; j++){
            if (ar == dp[j][j][j]){
                tuple[0] = p1;
                tuple[1] = p2;
                tuple[2] = p3;
                tuple[3] = j;
            }
        }
    }
    
    for (int i = 0; i < 3; i++) ans[tuple[i]] = tuple[3];
    
    if (tuple[3] == 1){
        vector <int> nv;
        for (int i = 1; i <= n; i++){
            if (ans[i] > 0) continue;
            
            int fetch = query(tuple[0], tuple[1], i);
            if (fetch == 0) {
                nv.push_back(i);
                if (nv.size() > 3) break;
            } else {
                ans[i] = 1;
            }
        }
        
        if (nv.size() == 0) print();
        
        vector <int> ntuple(3, -1);
        for (int i1 = 0; i1 < nv.size(); i1++){
            for (int i2 = i1 + 1; i2 < nv.size(); i2++){
                int ok = query(tuple[0], nv[i1], nv[i2]);
                
                for (int j = 2; j <= 4; j++){
                    if (ok == dp[1][j][j]){
                        ntuple[0] = nv[i1];
                        ntuple[1] = nv[i2];
                        ntuple[2] = j;
                    }
                }
            }
        }
        
        if (ntuple[0] == -1) print(false);
        ans[ntuple[0]] = ntuple[2];
        ans[ntuple[1]] = ntuple[2];
        
        tuple[0] = ntuple[0];
        tuple[1] = ntuple[1];
        tuple[2] = -1;
        tuple[3] = ntuple[2];
    }
    
    for (int i = 1; i <= n; i++){
        if (ans[i] > 0) continue;
        
        int fetch = query(tuple[0], tuple[1], i);
        for (int j = 1; j <= 4; j++){
            if (dp[tuple[3]][tuple[3]][j] == fetch)
                ans[i] = j;
        }
    }
    
    print();
}
 
int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 //   cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        Solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define all(x) x.begin(),x.end()

const int B = 31;

struct item {
	ll pos , bit, idx;
};

item make(ll pos , ll bit , ll idx){
	item res;
	res.pos = pos;
	res.bit = bit;
	res.idx = idx;
	return res;
}

void solve(){
    int n;
	cin >> n;
	int qu;
	cin >> qu;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	if(n == 1){
		while(qu--){
			int x;
			cin >> x;
			if(x < arr[0])cout << 1 << '\n';
			else cout << -1 << '\n';
		}
		return;
	}
	vector<pair<ll,ll>> v;
	queue<item> q;
	bool vis[n][B];
	memset(vis,0,sizeof vis);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < B; j++){
			if((arr[i] & (1 << j)) > 0){
				vis[i][j] = 1;
			}
		}
		v.pb(mp(i , arr[i]));
	}
	for(int i = 0; i < n - 1; i++){
		v.pb(mp(n+i,arr[i]|arr[i+1]));
	}
	for(int j = 0; j < B; j++){
		if(vis[n-1][j])q.push(make(n+n-1,j,0));
	}
	for(int i = 0; i < n - 1; i++){
		for(int j = 0; j < B; j++){
			if(vis[i][j])q.push(make(n+n+i,j,(i+1)%(n-1)));
		}
	}
	int val[n-1];
	for(int i = 0; i < n-1; i++)val[i] = arr[i]|arr[i+1];
	while(q.size()){
		item it = q.front();
		q.pop();
		if((val[it.idx] & (1 << it.bit)) > 0){
			continue;
		}
		val[it.idx] += (1 << it.bit);
		if(v.back().vf == it.pos){
			v.pop_back();
		}
		v.pb(mp(it.pos , val[it.idx]));
		q.push(make(it.pos + n , it.bit , (it.idx + 1)%(n-1)));
	}
	
	// first part gets over where v[i].first contains position in ascending order and v[i].second contains the value to what has become on that position.
	
	
	for(int i = 1; i < v.size(); i++){
		v[i].vs = max(v[i].vs , v[i-1].vs);
	}

	while(qu--){
		int x;
		cin >> x;
		ll l = 0 , r = v.size()-1;
		ll res = -1;
		while(l <= r){
			int mid = (l + r)/2;
			if(v[mid].vs <= x){
				l = mid + 1;
			}
			else {
				r = mid - 1;
				res = v[mid].vf+1;
			}
		}
		cout << res << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}