// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8
    }
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count the number
		// elements for each classifier as smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			// throw new IllegalArgumentException(
			//     "This node and target node may not already be related node may not already be related to this node");
			return thisRoot;
		}

		// Favor inserting the tree of lesser rank as a child of the tree with greater
		// rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count the number
		// elements for each classifier as smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			// throw new IllegalArgumentException(
			//     "This node and target node may not already be related node may not already be related to this node");
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count the number
		// elements for each classifier as smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count 
		// elements for each classifier as smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to the optimistic
		// best score provides a lookup mechanism from card values to equivalence classe.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic
		// best score provides a lookup mechanism from card values to equivalence classe.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic
		// best score provides mapping from card values to equivalence classe.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact that also 
	 * serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact
	 * that also serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact
	 * that serves as a facade for constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact
	 * and constructing a strategy object for the analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact
	 * and constructing a strategy object for second phase of analysis phase that follows the 
	 * present one.  The OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

public class Solution {
	private int[] A;
	private int[] B;

	// public static final int MAX_VALUE = 1000000000;
	// public static final int MAX_CARDS = 100000;

	public int solution(int[] A, int[] B) {
		this.A = A;
		this.B = B;

		final int initialDeckSize = A.length;
		final int initialMaximumScore = initialDeckSize + 1;

		BitSet loFound = new BitSet(initialMaximumScore);
		BitSet singles = new BitSet(initialMaximumScore);
		BitSet hiFound = new BitSet(initialMaximumScore);

		final OptimisticScoringStrategy optimisticScanFilter = 
			new OptimisticScoringStrategy(A, B, loFound, hiFound, singles);
		this.scanWithFilter(optimisticScanFilter);

		final OptimalScoringStrategy optimalScanFilter = optimisticScanFilter.close();
		this.scanWithFilter(optimalScanFilter);

		final int currentScore = optimalScanFilter.findOptimalScore();

		return currentScore;
	}


	private void scanWithFilter(CardFilteringStrategy filterStrategy) {
		final int filteringScore = filterStrategy.getFilteringScore();
		final int cardsStored = filterStrategy.getInputRowCount();

		for (int ii = 0; ii < cardsStored; ii++) {
			final int aVal = this.A[ii];
			final int bVal = this.B[ii];

			if (aVal < bVal) {
				if (bVal < filteringScore) {
					// A and B are possible score contributors. A is smaller.
					filterStrategy.onFlippableCard(ii, aVal, bVal);
				} else if (aVal < filteringScore) {
					// A is a possible score contributor. B is not.
					filterStrategy.onHalfValidCard(ii, aVal, bVal);
//				} else {
					// A and B are both rejected. A is smaller than B.
//					filterStrategy.onRejectedCard(ii, aVal, bVal);
				}
			} else if (bVal < aVal) {
				if (aVal < filteringScore) {
					// A and B are possible score contributors. B is smaller.
					filterStrategy.onFlippableCard(ii, bVal, aVal);
				} else if (bVal < filteringScore) {
					// B is a possible score contributor. A is not.
					filterStrategy.onHalfValidCard(ii, bVal, aVal);
//				} else {
					// A and B are both rejected. B is smaller than A.
//					filterStrategy.onRejectedCard(ii, bVal, aVal);
				}
			} else if (aVal < filteringScore) {
				// A and B are equal and their common value is a viable score contributor.
				filterStrategy.onMirroredCard(ii, aVal);
//			} else {
				// Both sides of the card have the same value, and its is too large to be
				// relevant.
//				filterStrategy.onRejectedCard(ii, aVal, bVal);
			}
		}

		filterStrategy.onTraversalCompleted();
	}
}

interface CardFilteringStrategy {
	public int getInputRowCount();

	public int getFilteringScore();

	public void onFlippableCard(int cardIndex, int lowValue, int highValue);

	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue);

	public void onMirroredCard(int cardIndex, int identicalValue);

//	public void onRejectedCard(int cardIndex, int lowValue, int highValue);

	public void onTraversalCompleted();
}

final class OptimisticScoringStrategy implements CardFilteringStrategy {
	private int[] A;
	private int[] B;
	private BitSet lowBits;
	private BitSet highBits;
	private BitSet singleBits;
	private int writeIndex;
	private int currentScore;
	private int optimisticScore;
	private int maximumScore;

	OptimisticScoringStrategy(int[] A, int[] B, BitSet lowBits, BitSet highBits, BitSet singleBits) {
		this.A = A;
		this.B = B;
		this.lowBits = lowBits;
		this.highBits = highBits;
		this.singleBits = singleBits;
		this.writeIndex = 0;
	}

	@Override
	public int getInputRowCount() {
		return this.A.length;
	}

	@Override
	public int getFilteringScore() {
		return this.A.length + 1;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		this.lowBits.set(lowValue);
		this.highBits.set(highValue);
		this.A[writeIndex] = lowValue;
		this.B[writeIndex++] = highValue;
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.lowBits.set(acceptedValue);
		this.singleBits.set(acceptedValue);;
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.lowBits.set(identicalValue);
		this.singleBits.set(identicalValue);;
	}

//	@Override
//	public void onRejectedCard(int cardIndex, int lowValue, int highValue) { }

	@Override
	public void onTraversalCompleted() {
		// Current score uses only the smaller value available from each filtered input card.
		// Optimistic score is found using all values available on either side of any filtered input card.
		//
		// Filtering applies a heuristic observation that no sequence will ever reach element numbers
		// that larger than the number of cards present in the deck, since each consecutive value consumes
		// another card from the deck.
		this.highBits.or(this.lowBits);
		this.currentScore = this.lowBits.nextClearBit(1);
		this.optimisticScore = this.highBits.nextClearBit(this.currentScore);
		this.maximumScore = this.writeIndex + this.singleBits.cardinality() + 1;
	}

	public int getCurrentScore() {
		return this.currentScore;
	}

	public int getOptimisticScore() {
		return this.optimisticScore;
	}
	
	public int getMaximumScore() {
		return this.maximumScore;
	}
	
	public BitSet getSingleBits() {
		return this.singleBits;
	}
	
	/**
	 * A convenience method for releasing memory held by this transient analysis artifact
	 * and constructing a strategy object for second phase of analysis.
	 * 
	 * OptimalScoringStrategy needs the optimistic score data value computed here.
	 * It also needs the compacted data set.
	 * 
	 * This class is able to get away with stripping single-valued cards from the retained rows because
	 * it retains a BitSet describing the values found in rows removed this way.
	 */
	public OptimalScoringStrategy close() {
		this.lowBits.clear();
		this.highBits.clear();

		final OptimalScoringStrategy retVal = new OptimalScoringStrategy(
			this.writeIndex, this.optimisticScore, this.lowBits, this.highBits, this.singleBits );

		this.A = this.B = null;
		this.highBits = this.lowBits = this.singleBits = null;
		
		return retVal;
	}
}

final class OptimalScoringStrategy implements CardFilteringStrategy {
	private final int cardsStored;
	private final int optimisticScore;
	private BitSet lowFlipBits;
	private BitSet highFlipBits;
	private BitSet singleBits;
	private ArrayList<EquivalenceClass> classByValue;
	private HashSet<EquivalenceClass> uniqueClassSet;

	OptimalScoringStrategy(int cardsStored, int optimisticScore, BitSet lowFlipBits, BitSet highFlipBits, BitSet singleBits) {
		this.cardsStored = cardsStored;
		this.optimisticScore = optimisticScore;
		this.lowFlipBits = lowFlipBits;
		this.highFlipBits = highFlipBits;
		this.singleBits = singleBits;
		
		this.singleBits.clear(optimisticScore, singleBits.size());

		this.classByValue = new ArrayList<EquivalenceClass>(this.optimisticScore);
		this.classByValue.add(null);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			this.classByValue.add(new EquivalenceClass(ii));
		}
	}

	@Override
	public int getInputRowCount() {
		return this.cardsStored;
	}

	@Override
	public int getFilteringScore() {
		return this.optimisticScore;
	}

	@Override
	public void onFlippableCard(int cardIndex, int lowValue, int highValue) {
		final EquivalenceClass lowClass = this.classByValue.get(lowValue);
		final EquivalenceClass highClass = this.classByValue.get(highValue);
		final EquivalenceClass unionClass;

		if (lowClass.isEquivalentTo(highClass)) {
			unionClass = lowClass;
		} else {
			final int lowLabel = lowClass.toLabel();
			final int highLabel = highClass.toLabel();

			unionClass = lowClass.unionWith(highClass);
			if (unionClass == lowClass) {
				this.classByValue.set(highValue, unionClass);
			} else {
				this.classByValue.set(lowValue, unionClass);
			}
		}

		this.highFlipBits.set(highValue);
		if (this.lowFlipBits.get(lowValue)) {
			unionClass.incrementCounter();
		} else {
			this.lowFlipBits.set(lowValue);

			if (this.singleBits.get(lowValue)) {
				unionClass.incrementCounter();
			}
		}
	}

	@Override
	public void onHalfValidCard(int cardIndex, int acceptedValue, int outOfRangeValue) {
		this.countSingleValuedCard(acceptedValue);
	}

	@Override
	public void onMirroredCard(int cardIndex, int identicalValue) {
		this.countSingleValuedCard(identicalValue);
	}
	
	private void countSingleValuedCard(int cardValue)
	{
		// Only compensate for the detection order between low and single valued
		// cards the first time either is encountered.
		if (this.singleBits.get(cardValue)) {
			return;
		}
		
		if (this.lowFlipBits.get(cardValue)) {
			final EquivalenceClass cardClass =
				this.classByValue.get(cardValue);
			cardClass.incrementCounter();
		}

		this.singleBits.set(cardValue);
	}

	@Override
	public void onTraversalCompleted() {
		// Count and path compress the remaining set of equivalence classes.
		this.uniqueClassSet = new HashSet<EquivalenceClass>(this.optimisticScore * 2);
		for (int ii = 1; ii < this.optimisticScore; ii++) {
			EquivalenceClass scoreClass = this.classByValue.get(ii);
			scoreClass = scoreClass.getRoot();
			this.classByValue.set(ii, scoreClass);
			this.uniqueClassSet.add(scoreClass);
		}
	}

	/**
	 * 
	 */
	public int findOptimalScore() {
		// For each bit of the candidate range for best-case achievable scores, we have
		// two bit maps indicating whether that value was or was not found:
		// 
		// (1) on a flippable card opposite another candidate value 
		// -or- 
		// (2) on a non-flippable card, either opposite an identical duplicate of
		// itself or an out-of-bounds value too large to fit into a one-based sequence
		// constrained card count.
		//
		// Any element found in (2) can be presumed always available without consuming
		// a flippable card.
		// 
		// Elements found in (1) have a calculated equivalence classifier. Two numbers
		// have the same equivalence class if and only if they are printed on opposite
		// sides of at least one deck card.  An array of size equal to optimistic best
		// score provides mapping from card values to equivalence classes.
		//
		// Once the equivalence classes as described above are identified, we can count
		// the number of cards belonging to each classifier.  We can also count how many
		// elements of each classifier are smaller on at least one card.  The difference
		// tells us how many cards can be considered "extra" as far as the smaller value
		// on each card is concerend, therefore how many times we can satisfy use one of
		// those cards to fill the gap sequence with the larger value from a card in
		// each equivalence class.

		this.highFlipBits.andNot(this.singleBits);
		this.highFlipBits.andNot(this.lowFlipBits);

		if (this.highFlipBits.isEmpty()) {
			// The optimistic score is generally unrealistic because it does not
			// account for values that have be satisfied using the larger value on
			// a card.  If we reach this instruction, we have discovered that we 
			// had no such need for the higher value from any card.  In this special
			// circumstance, we can just return the optimistic score and be done.
			return this.optimisticScore;
		}
		
		int currentCardValue =
			this.highFlipBits.nextSetBit(1);
		EquivalenceClass currentCardClass =
			this.classByValue.get(currentCardValue);
		int optimalScore =
			(currentCardClass.toCounter() == 0) ? currentCardValue : 0;
		while (optimalScore == 0) {
			currentCardClass.decrementCounter();
			final int nextCardValue =
				this.highFlipBits.nextSetBit(currentCardValue + 1);

			if (nextCardValue > 0) {
				currentCardClass = this.classByValue.get(nextCardValue);
				
				if (currentCardClass.toCounter() > 0) {
					currentCardValue = nextCardValue;
				} else {
					optimalScore = nextCardValue;
				}
			} else {
				optimalScore = this.singleBits.nextClearBit(currentCardValue + 1);
			}
		}

		return optimalScore;
	}
}

final class EquivalenceClass {
	private EquivalenceClass parent;
	private int label;
	private int counter;
	private int rank;

	public EquivalenceClass(int label)
	{
		this.parent = this;
		this.label = label;
		this.counter = 0;
		this.rank = 0;
	}

	public void setLabel(int label)
	{
		this.toRoot().label = label;
	}

	public int getLabel() {
		return this.getRoot().label;
	}

	public int toLabel() {
		return this.toRoot().label;
	}

	public void incrementCounter() {
		this.toRoot().counter += 1;
	}

	public int getCounter() {
		return this.getRoot().counter;
	}

	public int toCounter() {
		return this.toRoot().counter;
	}

	public boolean decrementCounter()
	{
		final EquivalenceClass counterClass = this.toRoot();
		if (counterClass.counter > 0) {
			counterClass.counter = counterClass.counter - 1;
			return true;
		}

		return false;
	}

	public boolean isEquivalentTo(EquivalenceClass candidate) {
		return (this.toRoot() == candidate.toRoot());
	}
	
	public boolean isRoot() {
		return this.parent == this;
	}

	public EquivalenceClass getRoot() {
		if (this.parent == this) {
			return this;
		}

		// Implement path compression to spare the cost of future lookups.
		this.parent = this.parent.getRoot();
		return this.parent;
	}
	
	private EquivalenceClass toRoot() {
		EquivalenceClass retVal = this.parent;
		while( retVal != retVal.parent ) {
			retVal = retVal.parent;
		}
		return retVal;
	}

	public EquivalenceClass unionWith(EquivalenceClass other)
	{
		final EquivalenceClass thisRoot = this.toRoot();
		final EquivalenceClass otherRoot = other.toRoot();

		if (thisRoot == otherRoot) {
			return thisRoot;
		}

		// Favor inserting tree of lesser rank as subtree of tree with greater rank.
		final EquivalenceClass retVal;
		final EquivalenceClass child;
		if (thisRoot.rank < otherRoot.rank) {
			retVal = otherRoot;
			child = thisRoot;
		} else { 
			retVal = thisRoot;
			child = otherRoot;

			if (thisRoot.rank == otherRoot.rank) {
				this.rank = this.rank + 1;
			}
		}
		
        retVal.counter = retVal.counter + child.counter;
		child.counter = 0;
		child.parent = retVal;

		return retVal;
	}
}