<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

410. Galaxy in danger
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Many years has already passed since the Logos galaxy was attacked by crazy space creatures, called mistkafers. With extreme efforts brave defenders of the galaxy managed to defeat the main forces of the opponent. The remaining enemies have been isolated on N different planets.

Now the Government of a galaxy has a very difficult problem — to get rid from mistkafers in a galaxy as soon as possible. Namely to take them far beyond the galaxy and to dump them into a black hole. To cope with this problem, the Government needs help of winged pferds which can fly through black holes.

By a strange coincidence, there is exactly N pferds available for the Government. Pferds can fly only all together, and each of them can transport to a black hole only one mistkafer per day. Thus, every day pferds take N mistkafers and transport them into a black hole. And every pferd is so logical and consecutive, that will take mistkafers from the same planet every time, and will not fly to a black hole without mistkafer. Therefore, if there is no mistkafers left on some planet, pferds cannot take them out further.

In order to prevent such situations, in the morning of each day the Government can send scientists to some of the planets. These scientists can clone mistkarefs (no matter how they do it, but after cloning the number of mistkafers on the planet is doubled). The cloning of mistkafers on one planet takes exactly one day, so that day pferds do not take off.

Find out the minimal number of days which is required to get rid of mistkafers.

Input
In the first line of the input file the amount of planets N (1 ≤ N ≤ 100000) is given. The second line contains N natural numbers, each of them means the number of mistkafers on a corresponding planet. The quantity of mistkafers on each planet does not exceed one billion.

Output
On the first line of the output file print one number K — the answer to the problem. In case the number of days does not exceed one thousand, in the following K lines output the description of days in the chronological order. If on the i-th day there was a flight of the pferds, output on (i+1)-th line a phrase "flying mission" (without quotes), otherwise output a phrase "science mission to the planet j (without quotes), where j — is the number of a planet on which the cloning was made.

Example(s)
sample input
sample output
2
1 2
3
science mission to the planet 1
flying mission
flying mission

sample input
sample output
2
2 1025
1035

<|response|>
## 1) Abridged problem statement (concise)

There are **N** planets, planet *i* initially has **a[i] ≥ 1** mistkafers.

Each day you choose exactly one action:

- **flying mission**: allowed only if all planets have at least 1 mistkafer; then
  `a[i] := a[i] - 1` for all *i* (so you remove exactly N mistkafers that day).
- **science mission to planet j**: no flight that day; instead
  `a[j] := 2 * a[j]`.

Find the **minimum number of days** to reach `a[i] = 0` for all planets.
Print that minimum **K**; if `K ≤ 1000`, also print one valid day-by-day plan.

Constraints: `1 ≤ N ≤ 100000`, `1 ≤ a[i] ≤ 1e9`.

---

## 2) Key observations

1. **Only flying decreases numbers.** Science only increases.
2. Let `M = max(a[i])`. The planet with `M` needs **at least M flying missions** to reach 0 (it can't be decreased in any other way).
   So `K ≥ M`.
3. If we decide to perform exactly **M flights**, then every planet must have "enough supply" to survive those flights (never hit 0 early). Planets with `a[i] < M` must be increased via doublings.
4. For a planet currently at value `x < M`, suppose we first do `s` flights (so everything decreases by `s`), then we do one doubling on this planet:
   - planet becomes `2(x - s)`
   - the "max trajectory" becomes `M - s`

   To perfectly synchronize the planet with the max afterward, we want:
   \[
   2(x-s) = (M-s) \Rightarrow s = 2x - M
   \]
   If `s` is feasible (`0 ≤ s ≤ x`), then **one well-timed science mission** (after exactly `s` flights) is enough for that planet.
5. If `2x - M < 0` (i.e. `x < M/2`), then no nonnegative `s` exists. The only fix is to **double immediately** (before any flights) until `x ≥ M/2`. After that, one timed doubling suffices.
6. This yields the minimum number of science missions per planet:
   - double immediately while `x < M/2`
   - then do exactly one timed double to match the max-trajectory
   (and if `x == M`, do nothing)

Total minimal days = `M + (total number of science missions)`.

---

## 3) Full solution approach

### Step A: Fix the number of flights
Compute `M = max(a)`. We will do exactly `M` flying missions (cannot do fewer; doing more is unnecessary if we avoid creating a new maximum).

Initialize `answer = M`.

### Step B: For each planet, compute needed science missions
For planet `i` with initial `x = a[i]`:

- If `x == M`: nothing needed.
- Else while `x < M`:
  - Compute `s = 2*x - M`.
  - If `0 ≤ s ≤ x`, then schedule **one** science mission for this planet **after `s` flights** (i.e., right before flight number `s+1`):
    - `answer += 1`
    - record operation `(s, i)` for output (if we will output the plan)
    - stop processing this planet.
  - Otherwise (`s < 0`), do an **immediate** science mission (before any flights):
    - `x *= 2`
    - `answer += 1`
    - record this operation in `pre_ops` (if output needed)

Each planet needs only `O(log M)` doublings, so total work is fast.

### Step C: Output schedule if `answer ≤ 1000`
We can print a valid plan:

1. Print all `pre_ops` first (these are science missions before any flights).
2. For `flight_day = 0..M-1`:
   - print all scheduled science missions with `s == flight_day`
   - print `"flying mission"`

This matches the intended timing: a science mission consumes a whole day, so it must be output as its own day, "inserted" before the corresponding flight.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int64_t> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // The problem asks for the least number of operations of either multiplying
    // by 2, or subtracting 1 from everything, required to make everything zero.
    // First we can notice that we need at least M = max(a) steps of
    // subtracting 1. We can show this is enough. Particularly, say we look at
    // some M/2 < x < M. Then with a single double, we can reach 2x >= M, and
    // there is no point in doubling further. But if we first subtract and then
    // double, we get to 2(x-1), while at that M := M - 1. What's more relevant
    // is the difference between M and x. Subtracting doesn't change it, while
    // doubling will overshoot it into 2(x-s)-(M-s) = 2x-M-s. Ideally we
    // shouldn't overshoot M, as that would create a new maximum. Therefore, we
    // can try to solve for s, or s = 2x-M. One constraint we have is that x >=
    // s >= 0. In other words we might have to first double until we reach a
    // point where we can actually match with M. After that point, we will find
    // s, wait for some subtraction steps (=s), double, and now have the two
    // positions will be equal. The above construction already performs M
    // subtracting steps, but we now need to make sure that doubling is also
    // optimal. This is not hard to notice, as the above approach will do
    // ~log(M/x) doubling steps, and this is the least we need, because we will
    // perform M subtracting steps anyways. We shouldn't forget that the problem
    // also asks for the actual construction if the answer is small enough.

    int64_t M = *max_element(a.begin(), a.end());
    int64_t ans = M;

    vector<vector<int>> ops(min(M, 1024ll));
    vector<int> pre_ops;
    for(int i = 0; i < n; i++) {
        int64_t x = a[i];
        while(x < M) {
            int64_t s = 2 * x - M;
            if(s >= 0 && s <= x) {
                ans++;
                if(0 <= s && s <= 1000) {
                    ops[s].push_back(i + 1);
                }
                break;
            }

            pre_ops.push_back(i + 1);
            ans++;
            x *= 2;
        }
    }

    cout << ans << endl;
    if(ans <= 1000) {
        for(int pos: pre_ops) {
            cout << "science mission to the planet " << pos << endl;
        }
        for(int i = 0; i < M; ++i) {
            for(int pos: ops[i]) {
                cout << "science mission to the planet " << pos << endl;
            }
            cout << "flying mission" << endl;
        }
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    a = list(map(int, data[1:1+n]))

    M = max(a)          # required number of flights at least
    ans = M             # start with M flight-days

    pre_ops = []        # immediate doublings (before any flights)

    # ops[s] = planets to double after exactly s flights
    cap = min(M, 1024)  # cap memory; only needed for small-day output anyway
    ops = [[] for _ in range(cap)]

    for i, x0 in enumerate(a):
        x = x0
        while x < M:
            # After s flights, x becomes x-s, M becomes M-s.
            # One doubling -> 2*(x-s). Match: 2*(x-s) == (M-s) => s = 2x - M
            s = 2 * x - M

            if 0 <= s <= x:
                ans += 1
                # Store if potentially printable and within ops array
                if s <= 1000 and s < cap:
                    ops[s].append(i + 1)  # 1-based planet index
                break

            # x too small -> must double immediately
            pre_ops.append(i + 1)
            ans += 1
            x *= 2

    out = [str(ans)]

    if ans <= 1000:
        # Print all immediate doublings first
        for p in pre_ops:
            out.append(f"science mission to the planet {p}")

        # Then M flights, inserting scheduled doublings before each flight
        for flight in range(M):
            if flight < cap:
                for p in ops[flight]:
                    out.append(f"science mission to the planet {p}")
            out.append("flying mission")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```

This approach runs in `O(N log M)` time and uses `O(N)` additional memory (plus small storage for printing when needed), which fits easily in the constraints.
