Try to make $$$\text{lcm}(c, d) = 1$$$.

What happens when $$$b = 1$$$?

We can solve this problem in $$$O(1)$$$ time by using a fixed constructive approach that works for any $$$n \ge 4$$$. Since we can choose any positive integers, we minimize the right side of the equation by setting $$$c = 1$$$ and $$$d = 1$$$, which makes $$$\text{lcm}(1, 1) = 1$$$. This simplifies our target condition to finding two numbers where $$$\gcd(a, b) = 1$$$ and their remaining sum is $$$a + b = n - 2$$$. To easily guarantee a GCD of $$$1$$$, we can fix $$$b = 1$$$, which leaves us with $$$a = n - 3$$$. Ultimately, the fixed tuple $$$(n - 3, 1, 1, 1)$$$ will always satisfy both the sum and the GCD-LCM constraints for any valid input.

• Time Complexity: $$$O(1)$$$
• Space Complexity: $$$O(1)$$$

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    cout << n - 3 << " " << 1 << " " << 1 << " " << 1 << "\n";
}

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

Let $$$p = x \bmod k$$$. Note that $$$p$$$ must be a strict divisor of $$$n$$$ such that $$$1 \le p \lt k$$$.

Since $$$k \le 1000$$$, we can iterate over all possible values of $$$p$$$ from $$$1$$$ to $$$k-1$$$ in $$$O(k)$$$ time.

For each valid $$$p$$$ where $$$n \bmod p == 0$$$, calculate $$$x = \frac{n}{p} \cdot k + p$$$ and find the minimum possible value.

$$$n$$$ has to be divisible by $$$p = x \bmod k$$$, which in turn is less than $$$k$$$. We can try all options of $$$p$$$ (in $$$O(p)$$$ time), and for suitable options restore $$$x = p \cdot \frac{n-p}{k}$$$. Choose the smallest possible $$$x$$$. Note that $$$p = 1$$$ always divides $$$n$$$, hence at least one option will always be available

• Time Complexity: $$$O(K)$$$
• Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const char nline = '\n';




int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   
    int n, k;
    cin >> n >> k;
    int tmp;
    for(int i = k-1; i >= 1; i--)
    {
        if(n%i == 0) {tmp = i; break;}
    }
    cout << k*(n/tmp)+tmp << endl;
}

Sort the array of farmer groups' demands first. Once the demands are in sorted order, think about how an optimal assignment of groups to the three leaders would look.

Suppose the leaders specialize in demands $$$x_1 \lt = x_2 \lt = x_3$$$. Will the groups assigned to each leader be scattered throughout the sorted array, or will each leader receive a contiguous segment?

Instead of directly finding the optimal specialization demands, binary search on the maximum allowed negotiation time $$$T$$$. For a fixed $$$T$$$, greedily assign the largest possible prefix to the first leader and the largest possible suffix to the third leader. Then check whether the remaining groups can all be covered by the second leader.

Let the three union leaders choose specialization demands $$$(x_1, x_2, x_3)$$$. Without loss of generality, assume that $$$x_1 \lt = x_2 \lt = x_3$$$ otherwise we simply renumber the leaders. When a farmer group arrives with primary demand $$$p$$$, the optimal strategy is to assign that group to the leader for whom $$$|x_i-p|$$$ is minimum, since this minimizes the negotiation time.

It follows that:

• The first leader will negotiate with groups whose demands lie from $$$1$$$ to $$$(x_1 + x_2) / 2$$$.
• The second leader will negotiate with groups whose demands lie from $$$(x_1 + x_2) / 2$$$ to $$$(x_2 + x_3) / 2$$$.
• The third leader will negotiate with groups whose demands lie from $$$(x_2 + x_3) / 2$$$ to $$$10^9$$$.

Therefore, after sorting the array of demands $$$a$$$, the first leader will always handle some prefix of the groups, the third leader will handle some suffix, and all remaining groups will be handled by the second leader.

Now we can binary search the answer.

To check whether a maximum negotiation time $$$T$$$ is achievable:

• Assign the largest possible prefix of the sorted demands to the first leader.
• Assign the largest possible suffix to the third leader.
• Finally, check whether all remaining demands lie inside an interval of length $$$2T$$$. If they do, a suitable specialization demand exists for the second leader (placing it at the midpoint of that interval), so every remaining group can be negotiated within time $$$T$$$.

The maximum prefix and maximum suffix can each be found with a single $$$O(n)$$$ scan of the sorted array.

• Time Complexity: $$$O(n log n)$$$ per test case, $$$O(N log N)$$$ overall where $$$N$$$ is the sum of $$$n$$$ over all test cases.
• Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vint vector<long long>
#define endl "\n"
bool check(int x, vint &a){
    int i1=upper_bound(a.begin(), a.end(), a[0]+2*x)-a.begin();
    int i2=lower_bound(a.begin(), a.end(), a[a.size()-1]-2*x)-a.begin();
    if(i1>=i2 || a[i2-1]-a[i1]<=2*x){
        return 1;
    }
    return 0;
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vint a(n);
        for(auto &i:a){
            cin >> i;
        }
        sort(a.begin(), a.end());
        int l=0, h=a[n-1];
        while(h-l>1){
            int mid=(h+l)/2;
            if(check(mid, a)){
                h=mid;
            }
            else{
                l=mid+1;
            }
        }
        if(check(l, a)){
            cout << l << endl;
        }
        else{
            cout << h << endl;
        }
    }
    return 0;
}

Think about the binary representation of $$$n$$$. What does each set bit represent if every group size must be a power of two?

Determine the minimum possible number of groups and the maximum possible number of groups that satisfy the conditions. When is the answer immediately $$$NO$$$?

Suppose you already have one valid representation of $$$n$$$ as a sum of powers of two. Can you repeatedly split a power of two into two equal halves? What effect does this have on the number of groups?

The minimum number of groups is equal to the number of set bits in the binary representation of $$$n$$$, because each set bit corresponds to one power of two.

If this minimum number is greater than $$$k$$$, it is impossible to form exactly $$$k$$$ groups. Similarly, if $$$k \gt n$$$, it is impossible since the smallest possible group size is $$$1$$$.

Otherwise, start with the powers of two corresponding to the set bits of $$$n$$$. Repeatedly choose any group whose size is greater than $$$1$$$ and split it into two equal groups. Each split:

• Preserves the total sum.
• Keeps every group size a power of two.
• Increases the number of groups by exactly one.

Continue performing splits until the number of groups becomes exactly $$$k$$$. Since $$$k \le n$$$, this process can always reach the desired number of groups.

• Time Complexity: $$$O(k \log k)$$$
• Space Complexity: $$$O(k)$$$

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> v;

    for (int i = 0; i < 32; i++)
        if ((1 << i) & n)
            v.push_back(1 << i);

    int index = 0;

    if (__builtin_popcount(n) > k || k > n)
    {
        cout << "NO";
        return 0;
    }

    k -= __builtin_popcount(n);

    while (k > 0 && index < v.size())
    {
        if (v[index] > 1)
        {
            v[index] /= 2;
            v.push_back(v[index]);
            k--;
        }
        else
        {
            index++;
        }
    }

    sort(v.begin(), v.end());

    cout << "YES\n";

    for (auto x : v)
        cout << x << " ";

    return 0;
}

Instead of trying to turn $$$a$$$ into $$$b$$$, think about how to turn $$$b$$$ back into the number it used to be. If the device "deleted" leading 1s to get $$$b$$$, how do you reverse that?

Reversing the deletion of a leading 1 simply means prepending a '1' to $$$b$$$. Mathematically, if $$$b$$$ has $$$D$$$ digits, prepending a 1 is exactly equivalent to adding $$$10^D$$$ to $$$b$$$.

The only other operation allowed is adding 9s. So, if we keep prepending 1s to $$$b$$$ to form a new target number $$$Req$$$, what mathematical condition must be true between $$$Req$$$ and $$$a$$$ so that we can bridge the gap purely by adding 9s?

Note that $$$10^k \equiv 1 \pmod 9$$$. This modular property guarantees that this process will always find a valid solution very quickly.

1.The Core Idea: Reconstructing the Target

Let's assume the register underwent some number of operations and eventually reached a massive value. Then, some number of leading 1s were deleted, leaving the value $$$b$$$. If we prepend those 1s back onto $$$b$$$, we reconstruct the temporary peak value of the register. Let's call this peak value $$$Req$$$. For example, if $$$b = 45$$$, and 2 leading ones were removed, $$$Req = 1145$$$. Because the only way the register's value increases is by adding 9s, the gap between the initial value $$$a$$$ and our peak value $$$Req$$$ must be entirely made up of 9s. This gives us two absolute conditions:

• $$$Req \ge a$$$ (We can only add 9s, so the peak must be greater than or equal to $$$a$$$).
• $$$(Req - a) \pmod 9 == 0$$$ (The difference must be exactly divisible by 9).

2.Prepending 1s Mathematically

If $$$b$$$ has $$$D$$$ digits, prepending a 1 is just $$$b + 10^D$$$. Prepending another 1 adds $$$10^{D+1}$$$, and so on. Every time we add a power of 10, what happens to the number modulo 9? Because $$$10 \equiv 1 \pmod 9$$$, it follows that $$$10^k \equiv 1 \pmod 9$$$ for any $$$k \ge 0$$$. This is the magic of the problem: Every time we prepend a 1, the value of $$$Req \pmod 9$$$ increases by exactly 1.

3.The Algorithm

• Start with $$$Req = b$$$.
• While $$$Req \lt a$$$, keep prepending 1s to $$$Req$$$. Keep track of how many 1s you add.
• Once $$$Req \ge a$$$, check if $$$(Req - a)$$$ is a multiple of 9.
• If it isn't, just keep prepending 1s! Because each prepended 1 increases the modulo remainder by exactly 1, you will find a perfect multiple of 9 in at most 8 more steps.
• Once $$$(Req - a) \pmod 9 == 0$$$, you are done. The number of 9s you need to add is $$$(Req - a) / 9$$$, and the number of leading 1s you need to drop is exactly the number of 1s you prepended.

Because we find a solution in just a handful of steps, the device is never Broken (it is always Stable), and the intermediate value will easily stay below $$$10^{18}$$$.

• Time Complexity: Time Complexity: $$$O(\log_{10} b)$$$ Calculating the initial number of digits takes $$$O(\log_{10} b)$$$ operations. The first while loop runs at most $$$\sim 10$$$ times (since $$$a \le 10^9$$$). The second while loop runs at most $$$8$$$ times because every iteration increments the value modulo 9 by exactly 1. Overall, the algorithm runs in $$$O(1)$$$ time relative to the constraints, easily passing any test case.

• Space Complexity: Space Complexity: $$$O(1)$$$ We only store a few long long variables and a vector of at most size 2. No arrays or heavy data structures are required.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long a, b;
    cin >> a >> b;
    
    long long req = b;

    long long temp_b = b;
    long long digits = 0;
    while (temp_b > 0) {
        digits++;
        temp_b /= 10;
    }
    
    long long inc = 1;
    for (int i = 0; i < digits; i++) {
        inc *= 10;
    }
    
    long long ones_prepended = 0;
    
    while (req < a) {
        req += inc;
        inc *= 10;
        ones_prepended++;
    }
    
    while ((req - a) % 9 != 0) {
        req += inc;
        inc *= 10;
        ones_prepended++;
    }
    
    cout << "Stable\n";
    
    vector<pair<string, long long>> operations;
    
    long long nines_added = (req - a) / 9;
    if (nines_added > 0) {
        operations.push_back({"+", nines_added});
    }
    if (ones_prepended > 0) {
        operations.push_back({"-", ones_prepended});
    }
    
    cout << operations.size() << "\n";
    for (auto op : operations) {
        cout << op.first << " " << op.second << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

Running a standard DFS to find the sum of distances from a single starting node takes $$$O(n)$$$ time. Doing this for all $$$n$$$ nodes takes $$$O(n^2)$$$, which is too slow. We need to reuse information to get an $$$O(n)$$$ solution.

Imagine you have already calculated the total delay for a root node $$$u$$$. If you shift your focus to its adjacent neighbor $$$v$$$, how does the total delay change?

When you move from $$$u$$$ to $$$v$$$ across a communication channel of weight $$$w$$$, some media organizations get closer by $$$w$$$, and the rest get further away by $$$w$$$. If you know the size of $$$v$$$'s subtree, you can calculate the new answer in $$$O(1)$$$ time.

1. The Core Idea: Rerooting Instead of calculating the answer for each node from scratch, we calculate the answer for an arbitrary root (let's say node 1). Then, we "reroot" the tree at its children, adjusting the answer based on how the distances change. This allows us to find the answer for all nodes in just two DFS passes.
2. Pass 1: Bottom-Up Tree DP (The Initial Root) In the first DFS, we root the tree at node 1. For every node $$$u$$$, we need to calculate: subtree_size[u]: The total number of nodes in the subtree rooted at $$$u$$$. The initial total delay for node 1. For a leaf node, its subtree size is $$$1$$$. For any other node, its subtree size is $$$1$$$ plus the sum of the subtree sizes of its children.
3. Pass 2: Top-Down DP (Moving the Root) Now, suppose we know the total delay for a parent node $$$P$$$, and we want to find the total delay for its child $$$C$$$. The edge connecting them has a verification delay (weight) of $$$w$$$. When we move the root from $$$P$$$ to $$$C$$$: All nodes in $$$C$$$'s subtree become closer by $$$w$$$. The total delay decreases by $$$w \cdot subtree_{size}[C]$$$. All other nodes in the tree (which is $$$n - subtree_{size}[C]$$$ nodes) become farther away by $$$w$$$. The total delay increases by $$$w \cdot (n - subtree_{size}[C])$$$. Combining these, the net change in the total delay is:

Therefore, the transition formula is:

• Time Complexity: $$$O(n)$$$ We perform exactly two Depth-First Searches. During both traversals, we visit each node and traverse each edge a constant number of times. The math transitions at each step take $$$O(1)$$$ time. Thus, the time complexity per testcase is $$$O(n)$$$. Over $$$t$$$ test cases, it scales proportionally to the sum of $$$n$$$, easily passing within the time limit.

• Space Complexity: $$$O(n)$$$ The graph is stored using an adjacency list which takes $$$O(n)$$$ memory (since there are $$$n-1$$$ edges in a tree). The subtree_size and ans arrays take $$$O(n)$$$ memory. The recursion stack depth during DFS can go up to $$$O(n)$$$ in the worst-case scenario (a degenerate line graph). Overall space complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<pair<int, long long>>> adj;
vector<int> subtree_size;
vector<long long> ans;

long long dfs_initial(int u, int parent) {
    long long total_delay_from_u = 0;
    subtree_size[u] = 1;

    for (auto edge : adj[u]) {
        int v = edge.first;
        long long w = edge.second;

        if (v != parent) {
            long long child_delay = dfs_initial(v, u);
            subtree_size[u] += subtree_size[v];
            total_delay_from_u += child_delay + (w * subtree_size[v]);
        }
    }
    return total_delay_from_u;
}

void dfs_reroot(int u, int parent) {
    for (auto edge : adj[u]) {
        int v = edge.first;
        long long w = edge.second;

        if (v != parent) {
            ans[v] = ans[u] + w * (n - 2LL * subtree_size[v]);
            dfs_reroot(v, u);
        }
    }
}

void solve() {
    cin >> n;
    
    adj.assign(n + 1, vector<pair<int, long long>>());
    subtree_size.assign(n + 1, 0);
    ans.assign(n + 1, 0);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    ans[1] = dfs_initial(1, -1);
    dfs_reroot(1, -1);

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Visualize the newly formed array as a sequence of blocks. The $$$1$$$st block contains the sums of all subarrays starting at index $$$1$$$. The $$$2$$$nd block contains sums of all subarrays starting at index $$$2$$$, and so on.

Instead of calculating the sum from $$$l$$$ to $$$r$$$ directly, write a function get_sum(k) that computes the sum of the first $$$k$$$ elements of the new array. Your answer for a query [l, r] then simply becomes get_sum(r) — get_sum(l — 1).

To quickly find the sum of a full block (or a partial block), you need the sum of subarray sums. If you create a prefix sum array of your standard prefix sum array (a double prefix sum), you can calculate the sum of any partial block in $$$O(1)$$$ time.

1. The Block Structure

Let your original array be $$$a$$$ (1-indexed). The new array $$$b$$$ is formed by blocks of subarray sums: Block 1 (length $$$n$$$): Subarrays starting at index 1 $$$\rightarrow [1, 1], [1, 2], \dots, [1, n]$$$ Block 2 (length $$$n-1$$$): Subarrays starting at index 2 $$$\rightarrow [2, 2], [2, 3], \dots, [2, n]$$$ Block $$$i$$$ (length $$$n-i+1$$$): Subarrays starting at index $$$i \rightarrow [i, i], [i, i+1], \dots, [i, n]$$$

2. The Math: Double Prefix Sums

Let $$$P$$$ be the standard prefix sum array where $$$P[i] = a[1] + a[2] + \dots + a[i]$$$. The sum of a subarray from index $$$i$$$ to $$$j$$$ is $$$P[j] - P[i-1]$$$. If we want the sum of the first $$$m$$$ elements of Block $$$i$$$, we are summing the subarrays ending at $$$j = i, i+1, \dots, i+m-1$$$. The sum of these $$$m$$$ elements is:

This can be split into:

To compute the sum of $$$P[j]$$$ efficiently, we just need a prefix sum of $$$P$$$ itself! Let's call this $$$PP$$$, where $$$PP[k] = P[1] + P[2] + \dots + P[k]$$$. Now, our formula for the first $$$m$$$ elements of Block $$$i$$$ becomes beautifully simple:

3. Answering Queries

To process get_sum(k): Use binary search (lower_bound) on an array that stores the ending index of each block to figure out which block the $$$k$$$-th element falls into. Add the total sums of all fully included preceding blocks. Use the double prefix sum formula above to add the remainder of the elements from the current block.

• Time Complexity: $$$O(n + q \log n)$$$ Precomputation ($$$O(n)$$$): Building the standard prefix sums (P), the double prefix sums (PP), and calculating the block details (block_sum, pref_block_sum, block_end_idx) all require a single pass through the array. This takes $$$O(n)$$$ time. Query Processing ($$$O(q \log n)$$$): For each of the $$$q$$$ queries, we call the get_sum function twice. Inside get_sum, we use lower_bound on the block_end_idx array (which is monotonically increasing) to find the correct block. Binary search takes $$$O(\log n)$$$ time. The subsequent math operations are all done in $$$O(1)$$$ time using our precomputed arrays. Thus, $$$q$$$ queries take $$$O(q \log n)$$$ time.
• Space Complexity: $$$O(n)$$$ We use a few $$$1$$$-dimensional arrays of size $$$n + 2$$$ (a, P, PP, block_sum, pref_block_sum, block_end_idx) to store our sequences and prefix sums. This takes $$$O(n)$$$ auxiliary space. The space required to process each query is strictly $$$O(1)$$$.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> P(n + 2, 0);
    for (int i = 1; i <= n; i++) P[i] = P[i - 1] + a[i];

    vector<long long> PP(n + 2, 0);
    for (int i = 1; i <= n; i++) PP[i] = PP[i - 1] + P[i];

    vector<long long> block_sum(n + 1, 0);
    vector<long long> pref_block_sum(n + 1, 0);
    vector<long long> block_end_idx(n + 1, 0);

    long long current_idx = 0;
    for (int i = 1; i <= n; i++) {
        long long len = n - i + 1;
        
        block_sum[i] = (PP[n] - PP[i - 1]) - len * P[i - 1];
        pref_block_sum[i] = pref_block_sum[i - 1] + block_sum[i];
        
        current_idx += len;
        block_end_idx[i] = current_idx;
    }

    auto get_sum = [&](long long k) -> long long {
        if (k == 0) return 0;
        
        int block = lower_bound(block_end_idx.begin() + 1, block_end_idx.end(), k) - block_end_idx.begin();
        
        long long ans = pref_block_sum[block - 1];
        
        long long rem = k - block_end_idx[block - 1];
        
        if (rem > 0) {
            ans += (PP[block + rem - 1] - PP[block - 1]) - rem * P[block - 1];
        }
        return ans;
    };

    int q;
    cin >> q;
    while (q--) {
        long long l, r;
        cin >> l >> r;
        cout << get_sum(r) - get_sum(l - 1) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

Notice that a subarray can shrink to a single value if and only if it can be split into two halves that each shrink to the same value. This structural property allows us to track the reduction values using an $$$O(n^3)$$$ interval DP table, $$$dp[l][r]$$$.

Given the constraint $$$n \le 500$$$, we can comfortably populate a 2D table $$$dp[l][r]$$$ which stores the collapsed value of the subarray $$$a[l \dots r]$$$ (or $$$-1$$$ if it is impossible to shrink). We can compute this by iterating over all possible lengths and testing all valid split points $$$k$$$ for each range.

Once the interval table is built, the problem reduces to finding the minimal block partition. We can solve this with a 1D prefix DP where $$$dp_2[i]$$$ represents the minimum length the prefix $$$a[1 \dots i]$$$ can be reduced to, transitioning through valid blocks $$$a[j + 1 \dots i]$$$ that fully collapse into a single element.

Let's look at the answer: by construction, each element in the final answer is the result of replacing a series of elements on a corresponding segment. Therefore, the problem reduces to finding the minimal (by size) partition of the array $$$a$$$ into segments such that each segment can be fully transformed into a single element by a series of replacements.

We can compute this final step using standard prefix dynamic programming. Let $$$dp_2[i]$$$ be the minimal partition size of a prefix of length $$$i$$$. The transitions are standard: we check all valid segments $$$[i + 1 \dots j]$$$ and, if that segment can be reduced to a single element, we relax the value of $$$dp_2[j]$$$:

Now, we need to efficiently determine for all segments of $$$a$$$ whether they can be replaced by exactly one element. We can calculate another table, $$$dp[l][r]$$$, which stores the value of the single element the subarray $$$a[l \dots r]$$$ reduces to (or $$$-1$$$ if it cannot be reduced).

To do this, we use the following structural observation: if a segment can be replaced by a single element, it either has a length of $$$1$$$ (base case), or it can be divided at some point $$$k$$$ into two parts such that: * The prefix $$$a[l \dots k]$$$ can be replaced by one element. * The suffix $$$a[k + 1 \dots r]$$$ can be replaced by one element. * The reduced values of these two parts are completely equal ($$$dp[l][k] = dp[k + 1][r]$$$).

If a valid split point $$$k$$$ exists, then the combined segment can be reduced to $$$dp[l][k] + 1$$$. These are exactly the transitions we need to check to compute $$$dp[l][r]$$$ via interval dynamic programming.

• Time Complexity: $$$O(N ^ 3)$$$
• Space Complexity: $$$O(N^2)$$$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));

    for (int i = 1; i <= n; ++i) {
        dp[i][i] = a[i];
    }

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            
            for (int k = l; k < r; ++k) {
                if (dp[l][k] != -1 && dp[k + 1][r] != -1 && dp[l][k] == dp[k + 1][r]) {
                    dp[l][r] = dp[l][k] + 1;
                    break;
                }
            }
        }
    }

    vector<int> min_partition(n + 1, INF);
    min_partition[0] = 0;

    for (int i = 0; i < n; ++i) {
        if (min_partition[i] == INF) continue;
        
        for (int j = i + 1; j <= n; ++j) {
            if (dp[i + 1][j] != -1) {
                min_partition[j] = min(min_partition[j], min_partition[i] + 1);
            }
        }
    }

    cout << min_partition[n] << "\n";
}

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