This is the algorithm that you are going to follow to come up with algorithmic solutions to problems.

Step-by-step routine to solve any problem (fast + correct)

1. Read & rephrase (30–90s). Read the statement twice. Rephrase it in one sentence and write it down. Identify input/output formats and example(s).
2. Scan constraints & goal. Note n, value ranges, number of tests. Decide required complexity (O(n), O(n log n), O(n²), …).
3. Work a tiny example by hand. Use the sample + one custom edge case (small, large, degenerate).

   Based on this, come up with observations about the problem we can leverage to simplify problem solving. Define it in terms of operations you know how to do (such as find predecessor or find rank).

   It is useful at this stage to redefine the problem in terms of invariants because these tend to be a easier to code into an algorithm.

4. Pick an approach & prove/cost it (2–5 min). Choose algorithm and prove correctness informally; estimate time & memory. If you can’t justify O(n) vs O(n²), pick the safer direction that fits constraints.
5. Outline steps & data structures. Write pseudocode or numbered steps. Decide types (int vs long), DS (array, deque, heap, map).
6. Write skeleton + IO first. Boilerplate: Fast input, output, main loop, parse T, placeholders for core functions.
7. Implement core logic in small functions. Keep functions short. Implement critical path first (the part that determines complexity).
8. Test on samples and quick edge cases. Run sample(s) → if WA/TLE, add prints / assertions locally, test extreme cases.
9. If WA: add more tests / stress test. Compare with brute force for random small cases when unsure.
10. Optimize only if necessary. If TLE, profile hot spots (avoid streams/generics in hot loops, reduce allocations).
11. Final sanity checks before submit. Off-by-one, overflow, negative modulus, reset between test cases, output format.
12. Submit. If WA/TLE, iterate: read editorial only after you’re reasonably stuck.

How to Data-Structure?

Sometimes we need to design data structure for our problem with knowledge of the operations that we need to perform. Here is how we can go about doing this in a reasonable manner:

1. List out the operations and guess the lowest possible complexity of the operations.
2. Then think about a naive solution that can do some operations well but are not adequate at others
3. Come up with a solution that you think deals with all operations effectively
4. Find its limitations [this is very important]. If there is any quirky property that you need to get rid of or difficult implementation details, then figure out how to make the solution more elegant
5. Do a thorough complexity analysis and come up with expected/amortized/worst-case analysis

Pointers that commonly trip you up (watch these)

• Misreading constraints / hidden assumptions. Always re-check limits (e.g., 10^5 vs 10^6 makes a big difference).
• Edge cases. Check mathematically that your code works for edge cases. This check could save you dozens of minutes!
• Off-by-one and index mixups. Be explicit whether indices are 0-based or 1-based; annotate loops.

  When index manipulation is needed, always work out which indices go on which ends before starting off.

• Integer overflow. Multiplication/addition can overflow int. When in doubt use long.
• Uninitialized / reused state across test cases. Clear arrays, maps, counters between tests.
• Wrong complexity estimate. Nested logs, sorts inside loops or re-hashing maps cause surprises.
• Mutable vs immutable confusion. Passing references or mutating shared data accidentally breaks logic.
• Floating-point precision & comparisons. Don’t compare doubles for equality; use epsilons.
• Assuming uniqueness or ordering. Problem may not guarantee that; don’t rely on it.
• Incorrect comparator for priority queue / sort. Comparator contract (transitivity) matters.
• Recursive depth limits. Java recursion depth ~10^4 may stackoverflow; convert to iterative when needed.
• Negative modulus results. Java’s % can be negative — normalize: (x % m + m) % m.
• Corner cases: empty/1-element structures. Always test n=0 / n=1.

Java-specific hacks, templates & pitfalls (copyable)

General tips

• Prefer primitive arrays (int[], long[]) over boxed collections (Integer[], List<Integer>) for speed & memory.
• Avoid Stream API and heavy use of generics inside hot loops — they’re elegant but slower.
• Use StringBuilder for building strings; avoid repeated String concatenation in loops.
• Pre-size ArrayList / HashMap if you know expected size to avoid rehash/resizing:

  newArrayList<>(expectedSize);
  newHashMap<>(initialCapacity,0.75f);
  
  

• For HashMap heavy use, set initial capacity to ceil(expected / loadFactor) to avoid rehash.

Fast IO (must have)

// Minimal fast scanner (works for contests)
import java.io.*;
import java.util.*;

classFastScanner {
privatefinal InputStream in;
privatefinalbyte[] buffer =newbyte[1<<16];
privateintptr=0, len =0;
    FastScanner(InputStream is){ in = is; }
privateintread()throws IOException {
if (ptr >= len) {
            len = in.read(buffer);
            ptr =0;
if (len <=0)return -1;
        }
return buffer[ptr++];
    }
    Stringnext()throws IOException {
StringBuildersb=newStringBuilder();
int c;
while ((c = read()) <=' ' && c != -1) {}
if (c == -1)returnnull;
do { sb.append((char)c); c = read(); }while (c >' ');
return sb.toString();
    }
intnextInt()throws IOException {return Integer.parseInt(next()); }
longnextLong()throws IOException {return Long.parseLong(next()); }
}

Use PrintWriter for output:

PrintWriterout=newPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));
out.println(ans);
out.flush();

Common templates

• Binary search (lower_bound style)

intlowerBound(int[] a,int x) {
intl=0, r = a.length;// answer in [0..n]
while (l < r) {
intm= l + (r - l)/2;
if (a[m] < x) l = m +1;
else r = m;
    }
return l;
}

• Modular arithmetic helpers

longmod=1_000_000_007L;
longmodAdd(long a,long b){ a += b;if (a >= mod) a -= mod;return a; }
longmodMul(long a,long b){return (a * b) % mod; }// cast to long before multiply
longmodPow(long a,long e){
longres=1;
while (e >0){
if ((e &1) ==1) res = modMul(res, a);
        a = modMul(a, a);
        e >>=1;
    }
return res;
}

(Important: cast operands to long before multiplication if they might be int.)

• Union-Find (fast)

classDSU {
int[] p, r;
    DSU(int n){ p =newint[n]; r =newint[n];for (int i=0;i<n;i++) p[i]=i; }
intfind(int x){return p[x]==x ? x : (p[x]=find(p[x])); }
booleanunion(int a,int b){
        a = find(a); b = find(b);if (a==b)returnfalse;
if (r[a] < r[b]) { p[a]=b; }elseif (r[b] < r[a]) { p[b]=a; }else { p[b]=a; r[a]++; }
returntrue;
    }
}

• Avoid recursion for deep trees/graphs — use an explicit stack for DFS.

Performance micro-hacks (use only when needed)

• Use Arrays.sort(int[]) for primitives; it’s fast (Dual-Pivot Quicksort for primitives).
• For counting/frequency with small alphabets, use arrays (e.g., int[26]) instead of maps.
• For maps keyed by integers in range [0..M), consider int[] or Trove-like libs (not in standard contests).
• If using PriorityQueue, prefer int[] paired with comparator via a single long key if you need speed.

Pitfalls to remember

• Integer vs int: == compares references for Integer (except for cached values). Use .equals() or primitives.
• Autoboxing causes allocations: avoid List<Integer> in hot loops.
• String.split() and regex-based parsing are slow — prefer token-based fast scanner.
• BigInteger is convenient but slow; use it only when truly necessary.
• Beware Math.multiplyExact throws ArithmeticException on overflow — use safe long casts instead.

Quick contest checklist