#include <bits/stdc++.h>
using namespace std;
int N, L, D;
vector<int> arr;
unordered_map<int, bool> dp; // memo for global DFS (key = used indices mask)
// Global DFS: try to partition the sorted array (of size N) into groups of size L with common difference D.
// mask: bitmask of indices already used.
bool dfs(int mask);
// Helper: given a fixed "base" (the smallest unused index in the current DFS call)
// and a candidate list (indices > base and unused), recursively choose L-1 indices
// to form a block with min = arr[base] and max = arr[base] + D.
// pos: current index in candidate vector to consider
// r: how many indices still need to be chosen
// found: whether we have already chosen an element equal to arr[base] + D
// currentSet: bitmask (with respect to global indices) of the candidates chosen so far.
bool chooseCombination(const vector<int> &candidates, int pos, int r, bool found, int currentSet, int base, int curMask) {
// If we have chosen enough indices, check that the block has the required max and try DFS on the new mask.
if(r == 0) {
if(!found) return false; // must have at least one candidate equal to arr[base] + D
int newMask = curMask | (1 << base) | currentSet;
if(dfs(newMask))
return true;
return false;
}
// Prune: if there are not enough remaining candidates
if(pos >= (int)candidates.size())
return false;
// Also, if we haven't found an element equal to arr[base]+D, check if any candidate in the remaining list can supply that.
bool canFindMax = found;
for (int i = pos; i < (int)candidates.size(); i++) {
if(arr[candidates[i]] == arr[base] + D) { canFindMax = true; break; }
}
if(!canFindMax) return false;
// Option 1: pick the candidate at pos.
int idx = candidates[pos];
bool newFound = found || (arr[idx] == arr[base] + D);
if(chooseCombination(candidates, pos + 1, r - 1, newFound, currentSet | (1 << idx), base, curMask))
return true;
// Option 2: skip the candidate at pos.
if(chooseCombination(candidates, pos + 1, r, found, currentSet, base, curMask))
return true;
return false;
}
bool dfs(int mask) {
if(mask == (1 << N) - 1) return true; // all indices used
if(dp.count(mask))
return dp[mask];
// Choose the smallest unused index as the base for the next block.
int base = 0;
while(mask & (1 << base)) base++;
// Gather candidate indices (all unused indices > base).
vector<int> candidates