There is a graph with N nodes from 0 to N-1.

For every two nodes X and Y where X<Y there is an undirected edge between X and Y with weight X^(X+1)^...^Y. This means that there are N*(N-1)/2 weighted edges.

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.

The value of an MST is defined as the sum of edge weights of edges used in MST.

Find the value of MST of the given graph.

Notes:

Here '^' means bitwise XOR operation.
A bitwise XOR is a binary operation that takes two-bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1.

Input Format
The first line contains an integer, N, denoting the number of nodes.

Constraints
1 <= N <= 10^5
Sample Input Sample Output Explanation
1 0 N=1 Since there is only 1 node and hence no edges so the value of MST will be 0.
3 4
N=3
Edges:
0-1 = 0^1 = 1.
0-2 = 0^1^2 = 3.
1-2 = 1^2 = 3.

We can use the edges 0-1 and 0-2, MST is 1+3=4.

4 1
N=4

There will be a total of 6 edges with weights:
0-1=0^1=1
0-2=0^1^2=3
0-3=0^1^2^3=0
1-2=1^2=3
1-3=1^2^3=0
2-3=2^3=1
In MST we can take edges (0,3), (1,3), and (2,3) hence the value of MST is 0+0+1=1.

import sys

def Solve(N):
# Write your code here

def main():
N = int(sys.stdin.readline().strip())

result = Solve(N)

print(result)

if name == "main":
main()

You are given an array A of N integers.

Additionally, it is given that a special segment K is a segment of an array that follows the given rules:

K is always non-empty.
K consists of contiguous elements.
K contains at least one non-empty subsequence that has a X-OR value equal to 0.

Find the maximum number of non-overlapping special segments such that each element in A is contained in exactly one special segment. Return 0 when there is no way to divide A as per the given conditions.

Input Format
The first line contains an integer, N, denoting the number of elements in A.
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing A[i].

Constraints
1 <= N <= 10^6
1 <= A[i] <= 10^9
Sample Input Sample Output Explanation
1
1 0
N = 1 A = [1] There is only one positive element, so the XOR is non-zero, hence the answer is 0.
3
1
2
3 1
N = 3 A = [1, 2, 3] There is only one segment that has a zero XOR subsequence because 1^2^3 = 0.
5
1
2
3
2
2 2
N = 5 A = [1, 2, 3, 2, 2] We can split the array into 2 segments {1,2,3} and {2,2}. The first segment contains {1,2,3} which has a subsequence {1,2,3} with xor = 0 The second segment contains {2,2} which has a subsequence with xor = 0
import sys

def NumOfMaxSeg(N, A):
# Write your code here

def main():
N = int(sys.stdin.readline().strip())

A = []
for _ in range(N):
    A.append(int(sys.stdin.readline().strip()))

result = NumOfMaxSeg(N, A)

print(result)

if name == "main":
main()

You are given a string s which consists only of the first 20 lowercase english letters.

The cost of a permutation P of the first 20 alphabet letters is defined as follows the number of adjacent letters s[i], s[i + 1] such that:

s[i + 1] appears before s[i] in the permutation P, or
s[i] == s[i + 1].

Find the minimum possible cost of creating a permutation using the first 20 lowercase english letters.

Notes:

A permutation of first 20 lowercase English letters is a string of size 20 which contains all 20 letters.

Input Format
The first line contains a string, s, denoting the given string s.

Constraints
1 <= len(s) <= 10^5
Sample Input Sample Output Explanation
abcde
0
S="abcde" any permutation P that starts with "abcde" is efficient enough to make the answer 0 since there will no pair of S[i] and S[i+1] where S[i+1] occurs before S[i] in the permutation P. Hence the answer is 0.
abcabcaa
3
S="abcabcaa" Here any permutation P which starts with "abc" will make the cost minimum since there will be 3 pairs (c,a) (c,a) and (a,a) where either S[i]=S[i+1] or S[i+1] occurs before S[i] .
aaabbbccc 6 S="aaabbbccc" Any permutation which starts which "abc" which will make the cost 6, since there are already 6 pairs where S[i]=S[i+1].

import sys

def getMin(s):

Write your code here

def main():
s = sys.stdin.readline().strip('\n')

result = getMin(s)

print(result)
if name == "main":
main()