Bit Counting Sequence (Problem C, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 2 sec
Author: Mitsuru Kusumoto

# Problem Statement

For a non-negative integer $x$, let $p(x)$ be the number of ones in the binary representation of $x$. For example, $p(26) = 3$ because $26 = (11010)_2$.

You are given a sequence of $n$ integers $(a_1, a_2, \ldots, a_n)$. Your task is to determine whether there exists a non-negative integer $x$ such that $(p(x), p(x+1), \ldots, p(x+n-1))$ is equal to $(a_1, a_2, \ldots, a_n)$. Furthermore, if it exists, compute the smallest $x$ satisfying the condition.

# Input

The first line of input contains one integer $t$ ($1 \leq t \leq 1000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line contains one integer $n$ ($1 \leq n \leq 500\,000$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 60$ for all $i$).

The sum of $n$ across all test cases in one input file does not exceed $500\,000$.

# Output

For each test case, output the smallest non-negative integer $x$ satisfying the condition above. If there is no such $x$, output $-1$ instead.


# Sample Input #1
```
4
5
3 3 4 1 2
3
2 1 2
2
60 60
2
8 0
```
# Sample Output #1
```
13
3
2305843009213693949
-1
```
*Explanation for the sample input/output #1*

For the first test case, $x = 13$ satisfies the condition above since $(p(13), p(14), p(15), p(16), p(17)) = (3, 3, 4, 1, 2)$.  
It can be shown that there is no non-negative integer smaller than $13$ that satisfies the condition above.

Sample inputs:
4
5
3 3 4 1 2
3
2 1 2
2
60 60
2
8 0

Sample outputs:
13
3
2305843009213693949
-1

# Solution Analysis
Analysis author: Mitsuru Kusumoto

**Observation C.1.** *For a non-negative integer $y$, if $p(y) - p(y + 1) = t \geq 0$, the rightmost $(t + 1)$ bits in the binary representation of $y$ are all 1. Additionally, the $(t + 2)$-th bit of $y$ from the right is 0.*

For example, consider $y = 87 = (1010111)_2$. Here, $t = p(y) - p(y + 1) = 5 - 3 = 2$. As the observation states, the rightmost three bits of $y$ are 1, and the fourth bit of $y$ from the right is 0.

Let $k$ be the smallest index such that $a_k = \max(a_1, \ldots, a_n)$. Also, let $x$ denote the solution to this problem.

When $k < n$, let $t = a_k - a_{k+1}$. It’s worth noting that $t \geq 0$ according to the definition of $k$. Based on the previous observation, the binary representation of $x + k - 1$ should be like

$$
x + k - 1 = (\ldots 0\underbrace{1\ldots1}_{t+1})_2.
$$

The bits starting from the $(t+3)$-th position from the right of $x + k - 1$ cannot be determined solely from this observation. However, considering that $a_k$ is the largest value among $a_1, \ldots, a_n$, for $s = a_k - (t + 1)$,

$$
x + k - 1 = (\underbrace{1\ldots1}_{s}0\underbrace{1\ldots1}_{t+1})_2.
$$

is the smallest possible value for $x + k - 1$. Consequently, we can compute the smallest possible value of $x$.  
If any of the following conditions hold: $s < 0$, $x < 0$, or $p(x + i - 1) \ne a_i$ for some $i$, then the solution does not exist.

Similarly, when $k = n$, the smallest possible value for $x + n - 1$ is $2^n - 1$. The runtime complexity is $\mathcal{O}(n)$.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}