<|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;

/*
  We compute:
  - M = max(a[i]) = required number of flights (at least).
  - For each planet with x < M:
      * While x < M:
           s = 2*x - M
           if 0 <= s <= x: schedule ONE timed doubling after s flights; done.
           else: do an immediate doubling (pre-op), x *= 2, continue.
  Total days = M + number_of_doublings.

  If total days <= 1000, output an explicit plan:
    - print all immediate doublings (pre_ops)
    - then for i=0..M-1:
         print all timed doublings scheduled at i
         print "flying mission"
*/

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

    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    long long M = *max_element(a.begin(), a.end());
    long long ans = M; // M flying missions for sure

    // If we need to print a plan (ans <= 1000), we store operations.
    // pre_ops: planets doubled before any flights.
    vector<int> pre_ops;

    // ops[s] = list of planets to double after exactly s flights
    // (i.e., right before flight s+1).
    // We only meaningfully need ops up to 1000 for printing; also if M is huge,
    // we don't want huge memory. 1024 is a safe cap.
    int cap = (int)min(M, 1024LL);
    vector<vector<int>> ops(cap);

    for (int i = 0; i < N; i++) {
        long long x = a[i];

        // If already max, it can survive M flights without any science.
        while (x < M) {
            // If we do s flights first, then one doubling,
            // want 2*(x - s) == (M - s)  => s = 2x - M
            long long s = 2 * x - M;

            if (0 <= s && s <= x) {
                // One timed science mission is enough.
                ans++;

                // Store only if we might print and index is within our cap.
                // Note: printing is required only if ans <= 1000 overall,
                // but we don't know it yet; still safe to store small s.
                if (s <= 1000 && s < cap) {
                    ops[(int)s].push_back(i + 1); // 1-based planet index
                }
                break;
            }

            // Otherwise x is too small (typically x < M/2), so we must double now.
            pre_ops.push_back(i + 1);
            ans++;
            x *= 2;
        }
    }

    cout << ans << "\n";

    // If answer is small enough, output the plan.
    if (ans <= 1000) {
        // First, all immediate doublings.
        for (int p : pre_ops) {
            cout << "science mission to the planet " << p << "\n";
        }

        // Then interleave timed doublings and flights.
        for (int flight = 0; flight < M; flight++) {
            if (flight < cap) {
                for (int p : ops[flight]) {
                    cout << "science mission to the planet " << p << "\n";
                }
            }
            cout << "flying mission\n";
        }
    }

    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.