Distinct Power
Source: codechef
Difficulty: 1699

Distinct Power
In the ancient kingdom of warriors, each troop possessed unique magical powers.
You are given an array$A$of$N$integers where$A_i$represents the power of the$i^{th}$troop. All powers in array$A$are
distinct
.
Each troop is assigned a rank based on its power - the troop with the highest power has rank$1$, and the troop with the lowest power has rank$N$. These ranks form array$B$. For example: If$A = [4, 5, 3, 7, 1, 9]$, then$B = [4, 3, 5, 2, 6, 1]$.
You need to remove exactly one troop from the array. When a troop is removed, the remaining troops are reranked from$1$to$N-1$based on their powers.
Find the number of
distinct
rank arrays possible after removing exactly one troop.
In simpler terms, count how many different arrays$B$of size$N-1$you can get after removing one troop and reranking the remaining troops.
Input Format
The first line of input contains a single integer$T$— the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains one integer$N$— the size of the array$A$.
The second line of each test case contains$N$space-separated integers$A_1,A_2,\ldots,A_N$, denoting the power of the$N$troops.
Output Format
For each test case, output on a new line, the number of distinct arrays$B$you can get after removing one troop from the array$A$.
Constraints$1 \leq T \leq 10^4$$2 \leq N \leq 3\cdot10^5$$1 \leq A_i \leq 10^9$The sum of$N$over all test cases won't exceed$3\cdot10^5$.
Sample 1:
Explanation:
Test case$1$:
On removing first troop,$A$becomes$[8,4,1]$and$B$becomes$[1, 2, 3]$.
On removing second troop,$A$becomes$[5,4,1]$and$B$becomes$[1, 2, 3]$.
On removing third troop,$A$becomes$[5,8,1]$and$B$becomes$[2, 1, 3]$.
On removing fourth troop,$A$becomes$[5,8,4]$and$B$becomes$[2, 1, 3]$.
Thus, two distinct arrays$B$are formed on removing one troop. They are$[1, 2, 3]$and$[2, 1, 3]$.
Test case$2$:
On removing first troop,$A$becomes$[1,4,12,7]$and$B$becomes$[4,3,1,2]$.
On removing second troop,$A$becomes$[9,4,12,7]$and$B$becomes$[2,4,1,3]$.
On removing third troop,$A$becomes$[9,1,12,7]$and$B$becomes$[2,4,1,3]$.
On removing fourth troop,$A$becomes$[9,1,4,7]$and$B$becomes$[1,4,3,2]$.
On removing fifth troop,$A$becomes$[9,1,4,12]$and$B$becomes$[2,4,3,1]$.
Thus, four distinct arrays$B$are formed on removing one troop.

Sample Input:
3
4
5 8 4 1
5
9 1 4 12 7
9
10 8 2 11 12 50 1 6 5

Sample Output:
2
4
5

C++ solution:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    int n; cin >> n;
    vector<pair<int,int>> a;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        a.emplace_back(x, i);
    }
    sort(a.begin(), a.end());
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = a[i].second;
    int ans = n;
    for (int i = 0; i + 1 < n; i++) {
        if (abs(p[i] - p[i + 1]) != 1) continue;
        int j = i + 1;
        while(j < n and abs(p[j - 1] - p[j]) == 1) j++;
        int len = j - i;
        ans -= len - 1;
        i = j - 1;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Go solution:
package main
import "fmt"
import "sort"
import "bufio"
import "os"

func main(){
    // your code goes here
    scanner := bufio.NewScanner(os.Stdin)
    maxCapacity := 500000
    buf := make([]byte, maxCapacity)
    scanner.Buffer(buf, maxCapacity)
    scanner.Split(bufio.ScanWords)
    scanner.Scan()
    var k int
    fmt.Sscanf(scanner.Text(), "%d", &k)
    for i := 0; i < k; i += 1 {
        scanner.Scan()
        var n int
        fmt.Sscanf(scanner.Text(), "%d", &n)
        
        power := make([]int, n)
        for j := 0; j < n; j += 1 {
            scanner.Scan()
            x := toInt(scanner.Bytes())
            
            power[j] = x
        }
        
        util := make([]int, len(power))
        for a := 0; a < len(util); a += 1 {
            util[a] = a
        }
        
        
        sort.Slice(util, func(i, j int) bool {
            return power[util[i]] > power[util[j]]
        })
        
        ranks := make([]int, len(power))
        for a, b := range util {
            ranks[b] = a + 1
        }
        
        var count int
        var prev int
        for a, rank := range ranks {
            diff := prev - rank
            if diff < 0 {
                diff *= -1
            }
            
            // fmt.Println("#################", prev, rank, diff)
            
            if a == 0 || diff > 1 {
                // fmt.Println("---------", a, diff)
                count += 1
            }
            
            prev = rank
        }
        // fmt.Println(ranks)
        fmt.Println(count)
    }
}

func toInt(buf []byte) (n int) {
    for _, v := range buf {
        n = n*10 + int(v-'0')
    }
    return
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), arr[][], n, i, rank[], count;
  
            while(__ -- > 0) {
                n = nextInt();
                arr = new int[n][2];
                for(i = 0; i < n; i++) {
                    arr[i][0] = nextInt();
                    arr[i][1] = i;
                }
                
                java.util.Arrays.sort(arr, (a, b) -> a[0] - b[0]);
                
                rank = new int[n];
                for(i = 0; i < n; i++) rank[i] = arr[i][1];
                
                count = 1;
                for (i = 1; i < n; i++) if(rank[i - 1] != rank[i] + 1 && rank[i - 1] != rank[i] - 1) count++;
                
                outData.append(count).append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

const f = require('fs');
const i = Buffer.allocUnsafe(1e7);
let p = 0,
        l = f.readSync(0, i, 0, i.length, null),
        o = Buffer.allocUnsafe(1e7),
        q = 0;

function r() {
        let n = 0,
                s = 1;
        while (i[p] < 48 || i[p] > 57) {
                if (i[p++] === 45) s = -1;
        }
        while (p < l && i[p] >= 48 && i[p] <= 57) n = n * 10 + (i[p++] - 48);
        return n * s;
}

function w(x, y = false) {
        if (q) o[q++] = 32;
        if (x < 0) {
                o[q++] = 45;
                x = -x;
        }
        let d = [];
        do {
                d.push(x % 10);
                x = ~~(x / 10);
        } while (x);
        for (let j = d.length - 1; j >= 0; j--) o[q++] = 48 + d[j];
        if (y) {
                o[q++] = 10;
        }
}

let t = r();
while (t--) {
        let n = r(),
                a = Array(n);
        for (let k = 0; k < n; k++) a[k] = r();
        let b = a.map((x, y) => [x, y]).sort((x, y) => y[0] - x[0]);
        let c = Array(n);
        for (let k = 0; k < n; k++) c[b[k][1]] = k + 1;
        let d = 0;
        for (let k = 0; k < n - 1; k++) {
                if (Math.abs(c[k] - c[k + 1]) === 1) d++;
        }
        w(n - d, true);
}

f.writeSync(1, o.slice(0, q));

Python solution:
def inps(): return map(int, input().split())
def lsinp(): return list(inps())


def solve():
    
    n = int(input())
    arr = lsinp()
    
    cpy = list(sorted(arr[:]))[::-1]
    
    power = {cpy[i] : i for i in range(n)}
    
    b = 0
    
    for i in range(n - 1):
        if abs(power[arr[i]] - power[arr[i+1]]) == 1:
            b += 1
    
    print(n - b)
        



for i in range(int(input())):
    solve()

Ruby solution:
def solve
  n = gets.to_i
  arr = gets.split.map(&:to_i)
  
  sorted = arr.sort.reverse
  power_rank = {}
  sorted.each_with_index do |val, index|
    power_rank[val] = index + 1  # Assigning ranks starting from 1
  end
  
  b = 0
  (0..n-2).each do |i|
    if (power_rank[arr[i]] - power_rank[arr[i+1]]).abs == 1
      b += 1
    end
  end
  
  puts n - b
end

t = gets.to_i
t.times { solve }