





import argparse
import collections
import json
import os
import re
import string
import sys

import numpy as np


UpperCAmelCase_      							=     re.compile(R"""\b(a|an|the)\b""", re.UNICODE)

UpperCAmelCase_      							=     None





def 						lowerCamelCase__     (     )			-> Any:



					'''simple docstring'''




					_snake_case									=				argparse.ArgumentParser('Official evaluation script for SQuAD version 2.0.'						)
					parser.add_argument('data_file'       ,    metavar='data.json'       ,    help='Input data JSON file.'						)
					parser.add_argument('pred_file'       ,    metavar='pred.json'       ,    help='Model predictions.'						)
					parser.add_argument(
					    '--out-file'       ,    '-o'       ,    metavar='eval.json'       ,    help='Write accuracy metrics to file (default is stdout).'						)
					parser.add_argument(
					    '--na-prob-file'       ,    '-n'       ,    metavar='na_prob.json'       ,    help='Model estimates of probability of no answer.'						)
					parser.add_argument(
					    '--na-prob-thresh'       ,    '-t'       ,    type=UpperCamelCase__       ,    default=1.0       ,    help='Predict "" if no-answer probability exceeds this (default = 1.0).'       ,    )
					parser.add_argument(
					    '--out-image-dir'       ,    '-p'       ,    metavar='out_images'       ,    default=UpperCamelCase__       ,    help='Save precision-recall curves to directory.'						)
					parser.add_argument('--verbose'       ,    '-v'       ,    action='store_true'						)
					if len(sys.argv						) == 1:
										parser.print_help()
										sys.exit(1						)
					return parser.parse_args()





def 						lowerCamelCase__     (     UpperCamelCase__			:       Optional[int]						)			-> Optional[Any]:



					'''simple docstring'''




					_snake_case									=				{}
					for article in dataset:
										for p in article["paragraphs"]:
															for qa in p["qas"]:
																				_snake_case									=				bool(qa['answers']['text']						)
					return qid_to_has_ans





def 						lowerCamelCase__     (     UpperCamelCase__			:       str						)			-> Optional[Any]:



					'''simple docstring'''




					def remove_articles(UpperCamelCase__			:       Tuple						):
										return ARTICLES_REGEX.sub(' '       ,    UpperCamelCase__						)

					def white_space_fix(UpperCamelCase__			:       str						):
										return " ".join(text.split()						)

					def remove_punc(UpperCamelCase__			:       List[str]						):
										_snake_case									=				set(string.punctuation						)
										return "".join(ch for ch in text if ch not in exclude						)

					def lower(UpperCamelCase__			:       List[Any]						):
										return text.lower()

					return white_space_fix(remove_articles(remove_punc(lower(UpperCamelCase__						)						)						)						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       Tuple						)			-> Optional[Any]:



					'''simple docstring'''




					if not s:
										return []
					return normalize_answer(UpperCamelCase__						).split()





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       Optional[Any]						)			-> Any:



					'''simple docstring'''




					return int(normalize_answer(UpperCamelCase__						) == normalize_answer(UpperCamelCase__						)						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       List[str]       ,    UpperCamelCase__			:       Tuple						)			-> List[str]:



					'''simple docstring'''




					_snake_case									=				get_tokens(UpperCamelCase__						)
					_snake_case									=				get_tokens(UpperCamelCase__						)
					_snake_case									=				collections.Counter(UpperCamelCase__						) & collections.Counter(UpperCamelCase__						)
					_snake_case									=				sum(common.values()						)
					if len(UpperCamelCase__						) == 0 or len(UpperCamelCase__						) == 0:
										# If either is no-answer, then F1 is 1 if they agree, 0 otherwise
										return int(gold_toks == pred_toks						)
					if num_same == 0:
										return 0
					_snake_case									=				1.0 * num_same / len(UpperCamelCase__						)
					_snake_case									=				1.0 * num_same / len(UpperCamelCase__						)
					_snake_case									=				(2 * precision * recall) / (precision + recall)
					return fa





def 						lowerCamelCase__     (     UpperCamelCase__			:       Optional[int]       ,    UpperCamelCase__			:       str						)			-> Tuple:



					'''simple docstring'''




					_snake_case									=				{}
					_snake_case									=				{}
					for article in dataset:
										for p in article["paragraphs"]:
															for qa in p["qas"]:
																				_snake_case									=				qa['id']
																				_snake_case									=				[t for t in qa['answers']['text'] if normalize_answer(UpperCamelCase__						)]
																				if not gold_answers:
																									# For unanswerable questions, only correct answer is empty string
																									_snake_case									=				['']
																				if qid not in preds:
																									print(F'''Missing prediction for {qid}'''						)
																									continue
																				_snake_case									=				preds[qid]
																				# Take max over all gold answers
																				_snake_case									=				max(compute_exact(UpperCamelCase__       ,    UpperCamelCase__						) for a in gold_answers						)
																				_snake_case									=				max(compute_fa(UpperCamelCase__       ,    UpperCamelCase__						) for a in gold_answers						)
					return exact_scores, fa_scores





def 						lowerCamelCase__     (     UpperCamelCase__			:       Union[str, Any]       ,    UpperCamelCase__			:       Optional[int]       ,    UpperCamelCase__			:       Tuple       ,    UpperCamelCase__			:       Union[str, Any]						)			-> Optional[Any]:



					'''simple docstring'''




					_snake_case									=				{}
					for qid, s in scores.items():
										_snake_case									=				na_probs[qid] > na_prob_thresh
										if pred_na:
															_snake_case									=				float(not qid_to_has_ans[qid]						)
										else:
															_snake_case									=				s
					return new_scores





def 						lowerCamelCase__     (     UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       List[Any]       ,    UpperCamelCase__			:       Optional[Any]=None						)			-> Any:



					'''simple docstring'''




					if not qid_list:
										_snake_case									=				len(UpperCamelCase__						)
										return collections.OrderedDict(
										    [
										        ('exact', 100.0 * sum(exact_scores.values()						) / total),
										        ('f1', 100.0 * sum(fa_scores.values()						) / total),
										        ('total', total),
										    ]						)
					else:
										_snake_case									=				len(UpperCamelCase__						)
										return collections.OrderedDict(
										    [
										        ('exact', 100.0 * sum(exact_scores[k] for k in qid_list						) / total),
										        ('f1', 100.0 * sum(fa_scores[k] for k in qid_list						) / total),
										        ('total', total),
										    ]						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       Optional[Any]       ,    UpperCamelCase__			:       str       ,    UpperCamelCase__			:       Optional[int]						)			-> List[str]:



					'''simple docstring'''




					for k in new_eval:
										_snake_case									=				new_eval[k]





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       Optional[int]       ,    UpperCamelCase__			:       Tuple       ,    UpperCamelCase__			:       int						)			-> str:



					'''simple docstring'''




					plt.step(UpperCamelCase__       ,    UpperCamelCase__       ,    color='b'       ,    alpha=0.2       ,    where='post'						)
					plt.fill_between(UpperCamelCase__       ,    UpperCamelCase__       ,    step='post'       ,    alpha=0.2       ,    color='b'						)
					plt.xlabel('Recall'						)
					plt.ylabel('Precision'						)
					plt.xlim([0.0, 1.05]						)
					plt.ylim([0.0, 1.05]						)
					plt.title(UpperCamelCase__						)
					plt.savefig(UpperCamelCase__						)
					plt.clf()





def 						lowerCamelCase__     (     UpperCamelCase__			:       Dict       ,    UpperCamelCase__			:       Tuple       ,    UpperCamelCase__			:       Union[str, Any]       ,    UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       Tuple=None       ,    UpperCamelCase__			:       Dict=None						)			-> List[Any]:



					'''simple docstring'''




					_snake_case									=				sorted(UpperCamelCase__       ,    key=lambda UpperCamelCase__						: na_probs[k]						)
					_snake_case									=				0.0
					_snake_case									=				1.0
					_snake_case									=				0.0
					_snake_case									=				[1.0]
					_snake_case									=				[0.0]
					_snake_case									=				0.0
					for i, qid in enumerate(UpperCamelCase__						):
										if qid_to_has_ans[qid]:
															true_pos += scores[qid]
										_snake_case									=				true_pos / float(i + 1						)
										_snake_case									=				true_pos / float(UpperCamelCase__						)
										if i == len(UpperCamelCase__						) - 1 or na_probs[qid] != na_probs[qid_list[i + 1]]:
															# i.e., if we can put a threshold after this point
															avg_prec += cur_p * (cur_r - recalls[-1])
															precisions.append(UpperCamelCase__						)
															recalls.append(UpperCamelCase__						)
					if out_image:
										plot_pr_curve(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__						)
					return {"ap": 100.0 * avg_prec}





def 						lowerCamelCase__     (     UpperCamelCase__			:       Optional[Any]       ,    UpperCamelCase__			:       str       ,    UpperCamelCase__			:       str       ,    UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       int       ,    UpperCamelCase__			:       Union[str, Any]						)			-> Union[str, Any]:



					'''simple docstring'''




					if out_image_dir and not os.path.exists(UpperCamelCase__						):
										os.makedirs(UpperCamelCase__						)
					_snake_case									=				sum(1 for v in qid_to_has_ans.values() if v						)
					if num_true_pos == 0:
										return
					_snake_case									=				make_precision_recall_eval(
					    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    out_image=os.path.join(UpperCamelCase__       ,    'pr_exact.png'						)       ,    title='Precision-Recall curve for Exact Match score'       ,    )
					_snake_case									=				make_precision_recall_eval(
					    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    out_image=os.path.join(UpperCamelCase__       ,    'pr_f1.png'						)       ,    title='Precision-Recall curve for F1 score'       ,    )
					_snake_case									=				{k: float(UpperCamelCase__						) for k, v in qid_to_has_ans.items()}
					_snake_case									=				make_precision_recall_eval(
					    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    out_image=os.path.join(UpperCamelCase__       ,    'pr_oracle.png'						)       ,    title='Oracle Precision-Recall curve (binary task of HasAns vs. NoAns)'       ,    )
					merge_eval(UpperCamelCase__       ,    UpperCamelCase__       ,    'pr_exact'						)
					merge_eval(UpperCamelCase__       ,    UpperCamelCase__       ,    'pr_f1'						)
					merge_eval(UpperCamelCase__       ,    UpperCamelCase__       ,    'pr_oracle'						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       str       ,    UpperCamelCase__			:       Dict       ,    UpperCamelCase__			:       List[str]       ,    UpperCamelCase__			:       List[Any]						)			-> Any:



					'''simple docstring'''




					if not qid_list:
										return
					_snake_case									=				[na_probs[k] for k in qid_list]
					_snake_case									=				np.ones_like(UpperCamelCase__						) / float(len(UpperCamelCase__						)						)
					plt.hist(UpperCamelCase__       ,    weights=UpperCamelCase__       ,    bins=20       ,    range=(0.0, 1.0)						)
					plt.xlabel('Model probability of no-answer'						)
					plt.ylabel('Proportion of dataset'						)
					plt.title(F'''Histogram of no-answer probability: {name}'''						)
					plt.savefig(os.path.join(UpperCamelCase__       ,    F'''na_prob_hist_{name}.png'''						)						)
					plt.clf()





def 						lowerCamelCase__     (     UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       Optional[int]       ,    UpperCamelCase__			:       Dict       ,    UpperCamelCase__			:       Tuple						)			-> List[str]:



					'''simple docstring'''




					_snake_case									=				sum(1 for k in qid_to_has_ans if not qid_to_has_ans[k]						)
					_snake_case									=				num_no_ans
					_snake_case									=				cur_score
					_snake_case									=				0.0
					_snake_case									=				sorted(UpperCamelCase__       ,    key=lambda UpperCamelCase__						: na_probs[k]						)
					for i, qid in enumerate(UpperCamelCase__						):
										if qid not in scores:
															continue
										if qid_to_has_ans[qid]:
															_snake_case									=				scores[qid]
										else:
															if preds[qid]:
																				_snake_case									=				-1
															else:
																				_snake_case									=				0
										cur_score += diff
										if cur_score > best_score:
															_snake_case									=				cur_score
															_snake_case									=				na_probs[qid]
					return 100.0 * best_score / len(UpperCamelCase__						), best_thresh





def 						lowerCamelCase__     (     UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       List[str]       ,    UpperCamelCase__			:       Tuple       ,    UpperCamelCase__			:       Any       ,    UpperCamelCase__			:       List[Any]       ,    UpperCamelCase__			:       List[str]						)			-> int:



					'''simple docstring'''




					_snake_case							,     _snake_case									=				find_best_thresh(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case							,     _snake_case									=				find_best_thresh(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				best_exact
					_snake_case									=				exact_thresh
					_snake_case									=				best_fa
					_snake_case									=				fa_thresh





def 						lowerCamelCase__     (     )			-> List[str]:



					'''simple docstring'''




					with open(OPTS.data_file						) as f:
										_snake_case									=				json.load(UpperCamelCase__						)
										_snake_case									=				dataset_json['data']
					with open(OPTS.pred_file						) as f:
										_snake_case									=				json.load(UpperCamelCase__						)
					if OPTS.na_prob_file:
										with open(OPTS.na_prob_file						) as f:
															_snake_case									=				json.load(UpperCamelCase__						)
					else:
										_snake_case									=				{k: 0.0 for k in preds}
					_snake_case									=				make_qid_to_has_ans(UpperCamelCase__						)  # maps qid to True/False
					_snake_case									=				[k for k, v in qid_to_has_ans.items() if v]
					_snake_case									=				[k for k, v in qid_to_has_ans.items() if not v]
					_snake_case							,     _snake_case									=				get_raw_scores(UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				apply_no_ans_threshold(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    OPTS.na_prob_thresh						)
					_snake_case									=				apply_no_ans_threshold(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    OPTS.na_prob_thresh						)
					_snake_case									=				make_eval_dict(UpperCamelCase__       ,    UpperCamelCase__						)
					if has_ans_qids:
										_snake_case									=				make_eval_dict(UpperCamelCase__       ,    UpperCamelCase__       ,    qid_list=UpperCamelCase__						)
										merge_eval(UpperCamelCase__       ,    UpperCamelCase__       ,    'HasAns'						)
					if no_ans_qids:
										_snake_case									=				make_eval_dict(UpperCamelCase__       ,    UpperCamelCase__       ,    qid_list=UpperCamelCase__						)
										merge_eval(UpperCamelCase__       ,    UpperCamelCase__       ,    'NoAns'						)
					if OPTS.na_prob_file:
										find_all_best_thresh(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__						)
					if OPTS.na_prob_file and OPTS.out_image_dir:
										run_precision_recall_analysis(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    OPTS.out_image_dir						)
										histogram_na_prob(UpperCamelCase__       ,    UpperCamelCase__       ,    OPTS.out_image_dir       ,    'hasAns'						)
										histogram_na_prob(UpperCamelCase__       ,    UpperCamelCase__       ,    OPTS.out_image_dir       ,    'noAns'						)
					if OPTS.out_file:
										with open(OPTS.out_file       ,    'w'						) as f:
															json.dump(UpperCamelCase__       ,    UpperCamelCase__						)
					else:
										print(json.dumps(UpperCamelCase__       ,    indent=2						)						)


if __name__ == "__main__":
					UpperCAmelCase_      							=     parse_args()
					if OPTS.out_image_dir:
										import matplotlib

										matplotlib.use("""Agg""")
										import matplotlib.pyplot as plt
					main()










def 						lowerCamelCase__     (     UpperCamelCase__			:       list						)			-> list:



					'''simple docstring'''




					_snake_case									=				len(UpperCamelCase__						)
					for i in range(1       ,    UpperCamelCase__						):
										_snake_case									=				collection[i]
										_snake_case									=				0
										_snake_case									=				i - 1

										while low <= high:
															_snake_case									=				(low + high) // 2
															if val < collection[mid]:
																				_snake_case									=				mid - 1
															else:
																				_snake_case									=				mid + 1
										for j in range(UpperCamelCase__       ,    UpperCamelCase__       ,    -1						):
															_snake_case									=				collection[j - 1]
										_snake_case									=				val
					return collection


if __name__ == "__main__":
					UpperCAmelCase_      							=     input("""Enter numbers separated by a comma:\n""").strip()
					UpperCAmelCase_      							=     [int(item) for item in user_input.split(""",""")]
					print(binary_insertion_sort(unsorted))



